Radar Installation
| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 93433 | Accepted: 20855 |
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.
Figure A Sample Input of Radar Installations
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
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
Source
题意：读入n和r，再读入n个坐标,表示每个海岛的位置，r是雷达覆盖范围，问最少需要多少个雷达覆盖全部海岛，如果不能全部覆盖，输出-1.雷达只能安装在x轴上。
思路：要找到最少雷达数，但是我们并不知道雷达位于x轴上哪个位置，所以我们可以以海岛坐标为圆中心点，以r为海岛的覆盖范围的圆与x轴交点所构成的区间就是雷达可以安装的区间，（假设r>海岛的纵坐标），因为在此区间任意位置安装雷达，都可以覆盖海岛，所以如果有另一个海岛雷达可安装区间和此海岛区间有公共区间，我们只要在公共区间内安装一个雷达即可覆盖两个海岛，以此类推，我们只需要算出最少的公共区间数就可以算出最少的雷达数。
要算出最少公共区间数，有两种思路：
第一种比较好理解一点（个人感觉~~毕竟是师父指点哒~~~）
按右端点从小到大进行排序，now_right初始化为第一个最小的右端点，并将此海岛标记为已经访问过，如果有未访问过的海岛的左端点next_left小于now_right，说明这两海岛存在公共区间，如果有未访问过得海岛的左端点next_left>now_right，说明它们之间不存在公共区间，雷达总数count增加，更新now_right为最新的海岛右端点。
#include<stdio.h> #include<math.h> #include<algorithm> using namespace std; #define N 1010 struct node{ double left,right;//左端点和右端点 int vis;//标记此海岛是否被访问过 }q[N]; double cmp(struct node a,struct node b)//结构体排序，由于是实数, 所以此处注意定义为double { if(a.right > b.right ) return a.right < b.right ; } int main() { int t = 0,n,r,count,i; double nowr,dis,x,y; while(scanf("%d%d",&n,&r),n!=0&&r!=0) { count = 1; if(r <= 0) count = -1; for(i = 0; i < n; i ++) { scanf("%lf%lf",&x,&y); if(fabs(y)> r) count = -1; else { dis = sqrt(r*r-y*y); q[i].left = x - dis; q[i].right = x +dis; q[i].vis = 0; } } if(count == -1) { printf("Case %d: %d ",++t,count); continue; } sort(q,q+n,cmp); nowr = q[0].right ;//用以判断是否存在公共区间的右端点初始化为第一个最小右端点 q[0].vis = 1;//第一个最小右端点标记为已经访问过 for(i = 1;i < n;i++) { if(!q[i].vis&&q[i].left > nowr)//如果海岛没有被访问过，并且此海岛左端点大于nowr，说明不存在公共区间 { q[i].vis = 1;//标记为访问过 nowr = q[i].right ;//更新右端点 count ++;//雷达数增加 } else if(!q[i].vis&&q[i].left < nowr)//如果存在公共区间，标记此海岛已经被访问过 q[i].vis = 1; } printf("Case %d: %d ",++t,count); } return 0; }
思路2：按左端点从小到大进行排序，如果存在下一个海岛的右端点小于当前海岛的右端点，说明它们之间存在公共区间。
这个思路有一个bug害的我找了半个小时，就是我定义存储当前海岛右端点的变量为int类型，可是，别人明明就是double型的啊，师父知道我犯这种错误，肯定特别无奈.............
#include<stdio.h> #include<math.h> #include<stdlib.h> #include<algorithm> using namespace std; #define N 1110 struct node{ double left,right; }q[N]; int cmp(struct node a,struct node b) { if(a.left == b.left ) return a.right < b.right ; return a.left < b.left ; } int main() { int n,r,i,count,flag,t=0; double dis,x,y,nowr; while(scanf("%d%d",&n,&r),n!=0&&r!=0) { flag = 0; if(r <= 0) { flag = 1; } for(i = 0; i < n; i ++) { scanf("%lf%lf",&x,&y);//此处注意定义x，y的类型 if(fabs(y) > r) flag = 1; else { dis = sqrt(r*r-y*y); q[i].left = x -dis; q[i].right = x + dis; } } if(flag) { printf("Case %d: -1 ",++t); continue; } sort(q,q+n,cmp); i = count = 1; nowr = q[0].right ;//nowr要定义为double型，否则精度丢失导致答案错误 while(i < n) { if(q[i].left > nowr)//下一个端点的左闭合点大于当前，说明无公共区间 { nowr = q[i].right ; count ++; } else if(q[i].right < nowr)//下一个端点的右区间小于当前，说明两者存在公共区间 nowr = q[i].right ; i++; } printf("Case %d: %d ",++t,count); } return 0; }