時間限制 2000 ms ・ 記憶體限制 256 MB
題目描述
海岸線是 x 軸，海洋位於 x 軸上方。每座小島以平面上的一個點表示。雷達必須安裝在海岸線上，可覆蓋與它的歐幾里得距離不超過 d 的小島。 給定全部小島的位置與共同覆蓋距離 d，求至少需要多少座雷達才能覆蓋所有島嶼。雷達的 x 座標不必是整數。如果不可能覆蓋所有小島，答案為 -1。
輸入格式
每筆第一行為兩個整數 n d，1 ≤ n ≤ 1000，n 是島嶼數。接著 n 行，每行兩個整數 x y 表示島嶼座標。相鄰資料以空白行分隔。以 0 0 結束。
輸出格式
資料從 1 起編號，每筆輸出 Case k: a，其中 a 是最少雷達數，無解時為 -1。
題目來源：UVa 1193 — Radar Installation。 原題：https://onlinejudge.org/external/11/1193.pdf
範例測資
範例輸入 1
3 2 1 2 -3 1 2 1 1 2 0 2 0 0
範例輸出 1
Case 1: 2 Case 2: 1
請先登入後再提交程式碼
討論與題解
載入討論區…