題目 1944:
藍橋杯算法提高VIP-Air Traffic Control
時間限制: 2s
內(nèi)存限制: 192MB 提交: 2 解決: 0
題目描述
為了避免空中相撞,大部分商業(yè)航班都被地面航空管制中心使用雷達跟蹤其位置來監(jiān)控。在這個問題中,你會被給予一組飛機和一組控制中心的信息,并計算出飛機是如何被控制中心監(jiān)控的(這句話的意思參考輸入描述:即計算恰好被K個控制中心監(jiān)控的飛機數(shù)目),飛機的位置用(x,y)坐標表示,基于此題的目的,無視飛機的高度(海拔)。
一個給定的控制中心能夠監(jiān)控的飛機數(shù)量因設(shè)備和工作人員的改變而時刻變化。在任一時刻,每一個控制中心會盡可能地監(jiān)控更多的飛機,它會按照如下優(yōu)先級選擇其監(jiān)控的飛機:1.離這個控制中心歐幾里得距離比較近的優(yōu)于比較遠的。2.若兩架飛機到控制中心的距離相同,那么選擇其中往北更遠的(y坐標軸正方向)。3.如果兩架飛機的距離和y坐標都相同,優(yōu)先選擇往東更遠的(x坐標正方向)。(補充說明:也就是說在距離相同的情況下,先比較y坐標,y坐標大的優(yōu)先級高,若y坐標依舊相同,x坐標大的優(yōu)先級高。數(shù)據(jù)會保證沒有任意兩個飛機的坐標相同。)
在任意時刻,每一個控制中心都有一個圓形“控制范圍”,其半徑等于其所監(jiān)控的最遠的那架飛機的距離。所有在控制范圍內(nèi)的飛機都被該控制中心監(jiān)控,但是在控制范圍邊界上的飛機可能或可能不被控制中心監(jiān)控,這取決于控制中心的容量和以上列出的優(yōu)先級。
你不會被告知控制中心的位置,取而代之的,對于每個控制中心,你會被告知它當前監(jiān)控的飛機個數(shù),以及其監(jiān)控范圍邊界上的兩點,用這些信息,你能計算出控制中心的位置,以及決定哪些飛機被其監(jiān)控。如果數(shù)據(jù)包含多種可能的監(jiān)控范圍,你應(yīng)該選擇包含了靠北最遠的那架飛機的,通過先選擇靠北最遠的再選擇靠東最遠的打破平局(——這段話的意思你可以這么認為:如果有多種可能的控制范圍以及對應(yīng)的控制中心位置滿足輸入要求,那么我們這么來判定:將飛機按照y坐標從大到小,y坐標相同的按照x從大到小排序,然后依次考慮,如果有架飛機在控制范圍A內(nèi),而其不在控制范圍B內(nèi),則我們會選擇A而不是B。注意,若兩個控制范圍監(jiān)控的飛機的集合相同,可以任意選擇一個,因為這不影響答案)。
下面這張圖展示了兩個控制中心和四架飛機的情況。每個控制中心用一個圓形控制區(qū)域和這個區(qū)域中的兩個點表示,用A和B標記。P1,P2,P3,P4標記了四架飛機。在這個例子中,飛機P1和P4都被一個單獨的控制中心監(jiān)視,而P3被兩個控制中心監(jiān)控,但P2卻沒有被任何一個控制中心監(jiān)控。
輸入格式
輸入包含多組測試數(shù)據(jù),每個數(shù)據(jù)第一行包括兩個正整數(shù)NP(0<NP<100)和NC(0<NC<10),分別表示了飛機的個數(shù)和控制中心的個數(shù)。接下來NP行,每行兩個浮點數(shù)表示一架飛機的(x,y)坐標。再接下來NC行,每行描述一個控制中心。首先是一個位于0到NP的正整數(shù)(包含0和NP),表示被該控制中心監(jiān)控的飛機個數(shù),然后是兩對浮點數(shù)表示監(jiān)控范圍邊界上的兩個位置的(x,y)坐標(兩個位置不會相同,而且也不會與飛機坐標重合)。注意:若兩個點之間的距離小于0.00001,你應(yīng)該將其視為一個點。
輸入以兩個0結(jié)束。
輸出格式
對于每組數(shù)據(jù),計算出被0個控制中心監(jiān)控的飛機個數(shù),被1個控制中心監(jiān)控的飛機個數(shù)等等,直到被NC個控制中心監(jiān)控的飛機個數(shù)。首先輸出數(shù)據(jù)組號,然后接下來NC+1個數(shù),序列中第ith數(shù)表示被i-1個控制中心監(jiān)控的飛機個數(shù)。如果某個控制中心不存在相符合的監(jiān)控范圍,那么輸出"Impossible"而不是相應(yīng)的序列。使用樣例中給定的輸出格式,然后每組數(shù)據(jù)之后都要輸出一個空行。
(關(guān)于輸出格式,請注意冒號之后有兩個空格,每個序列中每兩個數(shù)之間有兩個空格,序列的行末有兩個空格,Impossible后沒有空格,每組數(shù)據(jù)輸出占兩行。)
樣例輸入
4 2
3.0 0.0
0.0 0.0
1.6 2.8
2.0 1.0
2 1.0 2.0 2.0 0.0
2 2.0 2.0 4.0 2.0
2 1
0.0 0.5
0.0 -0.5
0 -1.0 0.0 1.0 0.0
0 0
樣例輸出
Trial 1: 1 2 1
Trial 2: Impossible
提示
零基礎(chǔ)同學(xué)可以先學(xué)習
視頻課程,包含C/C++、Python、百練、藍橋杯輔導(dǎo)、算法數(shù)據(jù)結(jié)構(gòu)等課程,提供視頻講解以及配套習題,還有老師答疑,
點擊這里了解課程詳情