Radar Installation POJ

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.

Figure A Sample Input of Radar Installations

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

Sample Output

Case 1: 2
Case 2: 1

百度翻译：

假设滑行是一条无限长的直线。陆地在海岸的一边，海洋在另一边。每个小岛都是一个位于海边的点。而且任何位于海岸的雷达装置只能覆盖d距离，所以如果它们之间的距离最多是d，那么海中的岛屿就可以被半径装置覆盖。我们使用笛卡尔坐标系，定义滑行是x轴。海平面在X轴以上，陆平面在X轴以下。考虑到每个岛屿在海上的位置，以及雷达装置覆盖范围的距离，您的任务是编写一个程序，以找到覆盖所有岛屿的雷达装置的最小数量。注意一个岛的位置由它的x-y坐标表示。”-1“安装意味着没有解决方案。

思路：可以看出这是个区间贪心问题，首先将每个海岛的能被雷达侦测范围求出，作为区间的左右两边。然后按照区间的左边由小到大排序。最后以每个区间的右侧作为标准，如果下一个区间的左侧与当前的标准大则再设一个雷达，同时标准改为下一个区间的右侧，当下一个区间的左侧比当前标准小则要考虑这个区间的右侧比标准小时，标准又要更换为这个区间的右侧。注意当海盗的y比雷达范围大时没有解决方案。

 1 #include <cstdio>
 2 #include <fstream>
 3 #include <algorithm>
 4 #include <cmath>
 5 #include <deque>
 6 #include <vector>
 7 #include <queue>
 8 #include <string>
 9 #include <cstring>
10 #include <map>
11 #include <stack>
12 #include <set>
13 #include <sstream>
14 #include <iostream>
15 #define mod 1000000007
16 #define eps 1e-6
17 #define ll long long
18 #define INF 0x3f3f3f3f
19 using namespace std;
20 
21 int m,n;
22 struct node
23 {
24     double zuo,you;
25 };
26 node no[1005];
27 bool px(node a,node b)
28 {
29     return a.zuo<b.zuo;
30 }
31 int main()
32 {
33     int a,b;
34     int s=0;
35     while(cin>>m>>n,m!=0,n!=0)
36     {
37         bool bo=false;
38         s++;
39         for(int i=0;i<m;i++)
40         {
41             cin>>a>>b;
42             no[i].zuo=a-sqrt(n*n*1.0-b*b);
43             no[i].you=a+sqrt(n*n*1.0-b*b);
44             if(b>n)
45             {
46                 bo=true;
47             }
48         }
49         if(bo)
50         {
51             printf("Case %d: -1
",s);
52         }
53         else
54         {
55             sort(no,no+m,px);
56             int ans=1;
57             double bj=no[0].you;
58             for(int i=1;i<m;i++)
59             {
60                 if(no[i].zuo>bj)
61                 {
62                     bj=no[i].you;
63                     ans++;
64                 }
65                 else
66                 {
67                     bj=min(bj,no[i].you);
68                 }
69             }
70             printf("Case %d: %d
",s,ans);
71         }
72 
73     }
74 }