Radar Installation
Time Limit : 2000/1000ms (Java/Other) Memory Limit : 20000/10000K (Java/Other)
Total Submission(s) : 47 Accepted Submission(s) : 25
Problem 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
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
题目分析：
纯数学问题结合贪心算法，很好理解的。就是在 x 上方有一些点，然后在X轴上建造一些雷达可以把这些点全给覆盖了，思路很简单，每一个点都对应一个区间在X轴上，这个就是数学问题了,区间为 [left=x-sqrt(d*d-y*y),right=x+sqrt(d*d+y*y)],这个区间就是以这个区间内的任意点为圆心都可以把这个点给覆盖了，现在是让你建造最少的雷达覆盖所有点，那么很简单，你先把数据定义一个结构体，然后以X轴从小到大排序，因为是要最少雷达吗，所以第一个点的圆心 right+d为边界，依次向正方向查看有几个点的横坐标比right+d大，查到一个就要更新此位置的right值然后接着查知道数据处理完，输出总个数就是最少雷达数。
<span style="font-size:18px;"><span style="font-size:18px;">#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
struct pos
{
int x;
int y;
}a[1010];
bool cmp(pos a,pos b)
{
return a.x<b.x;
}
int main()
{
int n,d,temp=0;
while(~scanf("%d%d",&n,&d)&&(n||d))
{
temp++;
printf("Case %d:\n",temp);
int i;
for(i=0;i<n;i++)
scanf("%d%d",&a[i].x,&a[i].y);
sort(a,a+n,cmp);
int ans=1;
//int l_x=a[0].x-sqrt(d*d-a[0].y*a[0].y);
double r_x=(double)(a[0].x+sqrt(d*d-a[0].y*a[0].y)+d);
for(i=1;i<n;i++)
{
if(1.0*a[i].x>r_x)
{
ans++;
r_x=(double)(a[i].x+sqrt(d*d-a[i].y*a[i].y)+d);
}
}
printf("%d\n",ans);
}
return 0;
}</span></span>
这是看别人写的感觉代码更好理解，但是思想相同。
/*2015-7-31 18:29:52
贪心。区间选点。
解题思路：
将二维坐标转换为一维坐标上的区间。求最小点覆盖所有区间。
如果小岛能被雷达覆盖，则转换在一维坐标上的最大区间为，[x-sqrt(d*d*1.0-y*y),x+sqrt(d*d*1.0-y*y)]
如果其中某个小岛不能被覆盖，则用标记变量标记。直接输出-1。
如果所有小岛都能被雷达覆盖，则进行贪心策略。
对所有区间右端进行从小大到排序（右端相同时，左端从大到小排序），则如果出现区间包含的情况，小区间一定排在前面。
然后开始遍历区间。如果当前区间超过上一个区间的覆盖范围，则雷达数+1。
第一个区间去最右值。
证明：如果第一个区间不取最右值，而取中间的点，那么把点移到最右端，被满足的区间增加了。而原先被满足的区间现在一定被满足。
*/
<span style="font-size:24px;">#include <cstdio>
#include <cmath>
#include <algorithm>
const int maxn = 1010;
using namespace std;
struct radar
{
double s,e;
}arr[maxn];
bool cmp(radar x,radar y)
{
if(x.e==y.e) return x.s>y.s;
else return x.e<y.e;
}
int main()
{
int n,d,i,x,y,flag,count;
int k=1;
double temp;
while(scanf("%d%d",&n,&d))
{
if(n==0&&d==0) break;
flag=0; //标记是否有小岛无法被覆盖
for(i=0;i<n;++i)
{
scanf("%d%d",&x,&y);
if(y>d)
{
flag=1; //如果雷达不足以覆盖，则标记
continue;
}
temp=sqrt(d*d*1.0-y*y);
arr[i].s=x-temp;
arr[i].e=x+temp;
}
printf("Case %d: ",k++);
if(flag)
{
printf("-1\n");
continue;
}
sort(arr,arr+n,cmp);
count = 1;
temp=arr[0].e;
for(i=1;i<n;++i)
{
if(arr[i].s>temp)
{
temp=arr[i].e;
count++;
}
}
printf("%d\n",count);
}
return 0;
}</span>