m644. 1193 - Radar Installation
標籤 :
通過比率 : 12人/13人 ( 92% ) [非即時]
評分方式:
Strictly

最近更新 : 2023-12-26 11:00

內容

假設海岸線是一條無窮直線。陸地位於海岸的一側,海洋位於另一側。每個小島都是海洋一側的一個點。而且,位於海岸上的任何雷達裝置只能涵蓋距離為d的範圍,因此海洋中的一個島嶼可以被雷達覆蓋,如果它們之間的距離最多為d。

我們使用笛卡爾坐標系統,將海岸定義為x軸。海洋一側在x軸上方,陸地一側在下方。給定每個島在海中的位置,並給定雷達裝置的覆蓋距離,您的任務是編寫一個程式,找到覆蓋所有島嶼所需的最小雷達裝置數量。請注意,島嶼的位置由其x-y坐標表示。

輸入說明

輸入包含多筆測資。
每筆測資的第一行包含兩個整數n(1 ≤ n ≤ 1000)和d,其中 n 是海洋中的島嶼數量,d 是雷達裝置的覆蓋距離。接下來有n行,每行包含兩個整數,表示每個島的位置座標。接著是一個空行,用於區分不同測資。

輸入以n=0 d=0 代表輸入終止。

輸出說明

對於每筆測資,輸出一行,包含測資編號,後面是所需的最小雷達裝置數。

如果某測資無解,請輸出 -1

範例輸入 #1
3 2
1 2
-3 1
2 1

1 2
0 2

0 0
範例輸出 #1
Case 1: 2
Case 2: 1
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (100%): 1.0s , <1M
提示 :
標籤:
出處:
UVA [管理者: yatsen (愛情少校) ]

本題狀況 本題討論 排行

編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」