Description
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 (1<=n<=1000) 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
大意：
有N个在X轴上方坐标已知的岛屿，然后有半径为d的雷达，只能放置在x轴上，问最少需要放置几个雷达才能覆盖所有的岛屿。如果无法覆盖输出-1。(Uva原题好像是这样的，不过听说POJ会输出在x轴下方的点?)
思路:
可以通过勾股定理算出点到圆心的距离在x轴上的投影，然后可以算出最左端和最右端的能覆盖该岛屿的雷达，确定每个岛屿能被覆盖的雷达放置区间(雷达被放在这个区间内可以覆盖该岛屿)。
之后对左端点进行排序，当前一个区间的末尾不能覆盖后一个区间的前端时，说明得多放一个雷达。
值得注意的是这里有个坑，当大区间包含一个小区间的时候，雷达放置在大区间的末尾可能覆盖不了小区间的末尾，产生错误解，所以要注意加个检测，当发现更左边的末端时，更新末端为它。
代码1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
using namespace std;
struct point{
double x, y, s, e;
};
bool cmp(point a,point b){
if(a.s==b.s){
return a.e < b.e;
}
else return a.s < b.s;
}
int main(){
int c=1;
while(1){
int n, i, ans = 0, f = 0;
double r;
cin >> n >> r;
if (r == 0 && n == 0)
{
break;
}
point a[n];
for (i = 0; i < n;i++){
scanf("%lf%lf", &a[i].x,&a[i].y);
if(a[i].y>r||a[i].y<0){
f = 1;
}
a[i].s = a[i].x - sqrt(r * r - a[i].y * a[i].y);
a[i].e = a[i].x + sqrt(r * r - a[i].y * a[i].y);
}
if(f){
cout << "Case " << c << ": " << -1 << endl;
c++;
continue;
}
sort(a, a + n, cmp);
i = 0;
while(i<n){
double s = a[i].e;
while (a[i].s<=s&&i<n){
if(a[i].e<s){
s = a[i].e;
}
i++;
}
ans++;
}
cout << "Case " << c << ": " << ans << endl;
c++;
}
return 0;
}