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
这题用的是贪心思想，对于每个小岛，可以在x轴上面把可以覆盖到此岛的区间算出来，即[x-sqrt(d*d-y*y),x+sqrt(d*d-y*y)],可以先对所有区间线段按右端点升序排序，然后依次找到最小的右端点，找到后所有左端点小于此右端点的记录一个标记b[i].vis=1,代表这条线段已经有点，往后就不用找了。这题也可以用另一种思路，所有区间线段按照左端点进行降序排序，初始的右端点记为s=b[1].r,如果后面的线段的左端点的值大于s,那么要加一个地雷点，且s=b[i].r,如果线段的右端点小于s,那么更新s=b[i].r.两种思路的本质其实是一样的。
思路一：
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
using namespace std;
struct node
{
double l,r;
int vis;
}b[1005];
bool cmp(node a,node b)
{
double temp;
if(a.r>b.r){
temp=b.l;b.l=a.l;a.l=temp;
return a.r<b.r;
}
return a.r<b.r;
}
int main()
{
double d,x,y;
int i,j,n,num,m=0,flag;
while(scanf("%d%lf",&n,&d)!=EOF)
{
m++;
if(n==0 && d==0)break;
flag=1;
memset(b,0,sizeof(b));
for(i=1;i<=n;i++){
scanf("%lf%lf",&x,&y);
if(y>d){
flag=0; //这里不要用break,因为数据还要输进去的。
}
b[i].l=x-sqrt(d*d-y*y);
b[i].r=x+sqrt(d*d-y*y);
}
if(flag==0){
printf("Case %d: -1
",m);continue;
}
sort(b+1,b+1+n,cmp);
num=0;
for(i=1;i<=n;i++){
if(b[i].vis==0){
num++;b[i].vis=1;
for(j=1;j<=n;j++){
if(b[j].l<=b[i].r){
b[j].vis=1;
}
}
}
}
printf("Case %d: %d
",m,num);
}
return 0;
}
思路二：
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
using namespace std;
struct node
{
double l,r;
}b[1005];
bool cmp(node a,node b)
{
double temp;
if(a.l>b.l){
temp=b.r;b.r=a.r;a.r=temp;
return a.l<b.l;
}
return a.l<b.l;
}
int main()
{
double d,x,y,s;
int i,j,n,num,m=0,flag;
while(scanf("%d%lf",&n,&d)!=EOF)
{
m++;
if(n==0 && d==0)break;
flag=1;
memset(b,0,sizeof(b));
for(i=1;i<=n;i++){
scanf("%lf%lf",&x,&y);
if(y>d){
flag=0;
}
b[i].l=x-sqrt((double)(d*d-y*y));
b[i].r=x+sqrt((double)(d*d-y*y));
}
if(flag==0){
printf("Case %d: -1
",m);continue;
}
sort(b+1,b+1+n,cmp);
num=1;
s=b[1].r;
for(i=2;i<=n;i++){
if(b[i].l>s){
num++;
s=b[i].r;continue;
}
if(b[i].r<s){
s=b[i].r;
continue;
}
}
printf("Case %d: %d
",m,num);
}
return 0;
}