假設海岸線是一條無窮直線。陸地位於海岸的一側,海洋位於另一側。每個小島都是海洋一側的一個點。而且,位於海岸上的任何雷達裝置只能涵蓋距離為d的範圍,因此海洋中的一個島嶼可以被雷達覆蓋,如果它們之間的距離最多為d。
我們使用笛卡爾坐標系統,將海岸定義為x軸。海洋一側在x軸上方,陸地一側在下方。給定每個島在海中的位置,並給定雷達裝置的覆蓋距離,您的任務是編寫一個程式,找到覆蓋所有島嶼所需的最小雷達裝置數量。請注意,島嶼的位置由其x-y坐標表示。
輸入包含多筆測資。
每筆測資的第一行包含兩個整數n(1 ≤ n ≤ 1000)和d,其中 n 是海洋中的島嶼數量,d 是雷達裝置的覆蓋距離。接下來有n行,每行包含兩個整數,表示每個島的位置座標。接著是一個空行,用於區分不同測資。
輸入以n=0 d=0 代表輸入終止。
對於每筆測資,輸出一行,包含測資編號,後面是所需的最小雷達裝置數。
如果某測資無解,請輸出 -1
3 2 1 2 -3 1 2 1 1 2 0 2 0 0
Case 1: 2 Case 2: 1
編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」
|