題目 1889:
藍橋杯算法提高VIP-Navigation
時間限制: 2s
內存限制: 192MB 提交: 1 解決: 0
題目描述
全球定位系統(tǒng)（GPS）是一個導航系統(tǒng)，根據(jù)一些在距地表大約20,000千米的軌道運行的衛(wèi)星。每個衛(wèi)星在一個已知的軌道上運行，發(fā)射編碼著當前時間的無線電信號。如果一個裝有全球定位系統(tǒng)的交通工具有一個非常精確的時鐘，它就可以比較它自己的當?shù)貢r間和從衛(wèi)星上接受到的編碼成信號的時間。因為無線電信號按一個已知的速度傳播，所以這個交通工具能夠計算出它目前的位置和信號發(fā)出時衛(wèi)星的位置之間的距離。通過測算這個交通工具和一些在已知軌道上運行的衛(wèi)星之間的距離，它可以非常精確地計算出自己的位置。
你必須寫一個簡單的“自動導航裝置”程序，根據(jù)GPS的導航。為了讓這個問題更簡單，我們描述一個二維的問題。換句話說，你不需要考慮地球的曲率或者衛(wèi)星的高度。此外，這個問題使用了更加適合于飛機和聲波的速度而不是衛(wèi)星和無線電波。
給定一組移動的信號源，你的程序必須計算出在笛卡爾平面內的接收點。然后，給定一個在平面內的目標點，你的程序必須計算出從接收點到目標點指南針的指向。所有的指南針的指向用角度表示。指南針指向0（北）相當于Y軸方向，指南針指向90（東）相當于X軸方向，就像圖1所展示的那樣。
你必須寫一個簡單的“自動導航裝置”程序，根據(jù)GPS的導航。為了讓這個問題更簡單，我們描述一個二維的問題。換句話說，你不需要考慮地球的曲率或者衛(wèi)星的高度。此外，這個問題使用了更加適合于飛機和聲波的速度而不是衛(wèi)星和無線電波。
給定一組移動的信號源，你的程序必須計算出在笛卡爾平面內的接收點。然后，給定一個在平面內的目標點，你的程序必須計算出從接收點到目標點指南針的指向。所有的指南針的指向用角度表示。指南針指向0（北）相當于Y軸方向，指南針指向90（東）相當于X軸方向，就像圖1所展示的那樣。
輸入格式
讀入包含多組測試數(shù)據(jù)。
每組數(shù)據(jù)的第一行包含一個整數(shù)N （1 ≤ N ≤ 10），表示信號源的數(shù)量。接下來有3個浮點數(shù)：t，x和y。這里，t表示當所有的信號被接收時精確的當?shù)貢r間，從基準時間（0時刻）按秒計時算起；x和y表示在笛卡爾平面內目標點的坐標。接下來N行每行包含4個浮點數(shù)，攜帶有1個信號源的信息。前2個數(shù)字表示信號源在基準時間在笛卡爾平面內的位置。第3個數(shù)字表示信號源向指南針指向D（0 ≤ D < 360）前進。第4個數(shù)字是編碼在信號里的時間——也就是，信號發(fā)出的時間，從基準時間按秒計時算起。輸入文件所有數(shù)字小于10000，沒有一個浮點數(shù)在小數(shù)點后超過5位。
最后一組數(shù)據(jù)的接下來一行包含4個0。
坐標系的單位距離是1m。假設每個信號源以100m/s的速度在笛卡爾平面上移動，信號以350m/s的速度傳播。由于時鐘同步的不精確，你計算的距離都只精確到0.1m。也就是說，如果2個點相距0.1m以內，你應該把它們看成相同的點。信號可能在傳播途中被干擾，所以接收到的多個信號可能會矛盾。
每組數(shù)據(jù)的第一行包含一個整數(shù)N （1 ≤ N ≤ 10），表示信號源的數(shù)量。接下來有3個浮點數(shù)：t，x和y。這里，t表示當所有的信號被接收時精確的當?shù)貢r間，從基準時間（0時刻）按秒計時算起；x和y表示在笛卡爾平面內目標點的坐標。接下來N行每行包含4個浮點數(shù)，攜帶有1個信號源的信息。前2個數(shù)字表示信號源在基準時間在笛卡爾平面內的位置。第3個數(shù)字表示信號源向指南針指向D（0 ≤ D < 360）前進。第4個數(shù)字是編碼在信號里的時間——也就是，信號發(fā)出的時間，從基準時間按秒計時算起。輸入文件所有數(shù)字小于10000，沒有一個浮點數(shù)在小數(shù)點后超過5位。
最后一組數(shù)據(jù)的接下來一行包含4個0。
坐標系的單位距離是1m。假設每個信號源以100m/s的速度在笛卡爾平面上移動，信號以350m/s的速度傳播。由于時鐘同步的不精確，你計算的距離都只精確到0.1m。也就是說，如果2個點相距0.1m以內，你應該把它們看成相同的點。信號可能在傳播途中被干擾，所以接收到的多個信號可能會矛盾。
輸出格式
對于每組數(shù)據(jù)，輸出數(shù)據(jù)的編號和從接收位置到目的地指南針的指向，用角度表示，四舍五入到整數(shù)。使用在樣例輸出中展示的標識。如果信號包含不夠多的信息來計算接收位置（也就是，符合所有信號的超過一個位置），輸出“Inconclusive”。如果信號矛盾（也就是，沒有位置符合所有的信號），輸出“Inconsistent”。如果接收位置相距目的地0.1m以內，輸出“Arrived”。如果情形是Inconclusive或者Inconsistent，那么你不需要考慮Arrived的情形。
圖2對應著樣例的第一個數(shù)據(jù)。t=0時3個衛(wèi)星的位置A（-100，350），B（350，-100），和C（350，800）。被GPS裝置接收的信號都在t=1.75時被發(fā)出，當衛(wèi)星處在位置A'，B'，C'的時候（然而，通常被GPS裝置接收的信號發(fā)出的時刻是不同的）。3個衛(wèi)星發(fā)出信號在t=2.53571時刻匯聚在D，意味著D是接收信號的GPS裝置的位置。從點D出發(fā)，指南針指向45度最終會到達目的地（1050，1050）。
圖2對應著樣例的第一個數(shù)據(jù)。t=0時3個衛(wèi)星的位置A（-100，350），B（350，-100），和C（350，800）。被GPS裝置接收的信號都在t=1.75時被發(fā)出，當衛(wèi)星處在位置A'，B'，C'的時候（然而，通常被GPS裝置接收的信號發(fā)出的時刻是不同的）。3個衛(wèi)星發(fā)出信號在t=2.53571時刻匯聚在D，意味著D是接收信號的GPS裝置的位置。從點D出發(fā)，指南針指向45度最終會到達目的地（1050，1050）。
樣例輸入
3 2.53571 1050.0 1050.0 -100.0 350.0 90.0 1.75 350.0 -100.0 0.0 1.75 350.0 800.0 180.0 1.75 2 2.0 1050.0 1050.0 -100.0 350.0 90.0 1.0 350.0 -100.0 0.0 1.0 0 0 0 0
樣例輸出
Trial 1: 45 degrees Trial 2: Inconclusive