Morris' Blog 我在摸索我存在的意義、生命的意義、內涵及價值。 沒有真正神手般的厲害，套用模式是大部分的情況。 沒那麼厲害的我存在的意義為何，襯托出神的存在？ 有時候不能怪別人不給我機會，我已經開始省思， 為什麼我沒有給別人機會的原因，而是全要靠別人。 有時候我認為我與眾不同，那是因為我做不到很多人能辦到的事情。 我聽不到、玩不起來、說得不夠明瞭、理解得不夠多， 我缺少的語文能力，就是一切一切無能的判定。 為此，我不曉得能做些對別人有幫助的事情。 我知道我自己是個不服輸的性格，但現在我不得不認輸。 我沒有能力，因此我必須認輸。 我到底來這世界作什麼？處處充滿不確定性， 而我總是無法出類拔萃，想當個一般人似乎也回不了頭了。 越強大的挑戰需要越強力的支持，而我的支持是什麼？ 最近嘗試與人談話，但都是失敗的結局，沒人能接受， 不需要言語，不需要溝通，一切所想都表達不出來。

49愛的鼓勵 6訂閱站台

Assume the coasting is an infinite straight line. Land is in one side of coasting, sea in the other. Each small island is a point locating in the sea side. And any radar installation, locating on the coasting, can only cover d distance, so an island in the sea can be covered by a radius installation, if the distance between them is at most d .

We use Cartesian coordinate system, defining the coasting is the x -axis. The sea side is above x -axis, and the land side below. Given the position of each island in the sea, and given the distance of the coverage of the radar installation, your task is to write a program to find the minimal number of radar installations to cover all the islands. Note that the position of an island is represented by its x -y coordinates.

Input 

The input consists of several test cases. The first line of each case contains two integers n (1n1000) and d , where n is the number of islands in the sea and d is the distance of coverage of the radar installation. This is followed by n lines each containing two integers representing the coordinate of the position of each island. Then a blank line follows to separate the cases.

The input is terminated by a line containing pair of zeros.

Output 

For each test case output one line consisting of the test case number followed by the minimal number of radar installations needed. `-1' installation means no solution for that case.

Sample Input 

3 2
1 2
-3 1
2 1

1 2
0 2

0 0

Sample Output 

Case 1: 2
Case 2: 1

---

題目描述：
用最少的偵測器覆蓋海外所有小島，偵測器彼此之間沒有任何關係(即不用重疊)。
而每個偵測器都張開半徑 d 的圓。

題目解法：
明顯地會發現，考慮一個最左邊的點(小島)，這個點一定在圓上，會盡可能覆蓋右方的點。
然後把可覆蓋的點都去掉，重覆這個步驟。

如果轉換成區間操作的時候，要記得是對點做排序，而非對區間做排序。
區間可以當作這個點，偵測器可以放置的可行解，因此要找有一個交集的最大量集合。

會有大的區間覆蓋小的區間，也就是 [()] 的樣子，那麼必須將右範圍縮小。

#include <stdio.h>
#include <math.h>
#include <algorithm>
using namespace std;

int main() {
    int n, cases = 0;
    int i;
    double x, y, d;
    pair<double, double> pt[1005];
    while(scanf("%d %lf", &n, &d) == 2) {
        if(n == 0)  break;
        int flag = 0;
        for(i = 0; i < n; i++) {
            scanf("%lf %lf", &x, &y);
            pt[i] = make_pair(x, y);
            if(y > d)
                flag = 1;

        }
        /*

12 21
27 1
16 19
12 6
-12 17
-2 16
-49 4
-13 12
46 12
48 4
-46 6
26 14
-22 10
        */
        if(flag) {
            printf("Case %d: %d\n", ++cases, -1);
            continue;
        }
        sort(pt, pt+n);
        for(i = 0; i < n; i++) {
            x = pt[i].first, y = pt[i].second;
            double td = sqrt(d*d - y*y) + 1e-8;
            pt[i] = make_pair(x-td, x+td);
        }
        int ret = 0;
        double r = -(1e+60);
        i = 0;
        while(i < n) {
            while(i < n && pt[i].first <= r) {
                r = min(r, pt[i].second);
                i++;
            }
            r = pt[i].second;
            ret++;
        }
        printf("Case %d: %d\n", ++cases, ret-1);
    }
    return 0;
}