POJ1328 Radar Installation区间贪心
Radar Installation
来源：http://poj.org/problem?id=1328
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 112280 Accepted: 24755
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
题意：
就是雷达放x轴上，探测范围为d为半径的圆，小岛在第一第二象限，要你用最少的雷达数覆盖所有小岛。如果其中有一个岛找不到就输出-1。
分析:
1.先要把问题进行转化一下，转化为如果想要探测到小岛，雷达应该放在x轴的哪一个范围内，方法就是以岛为圆心，作半径为d的圆，该圆与x轴的交点间的范围就是要探测该岛雷达可以放置的位置。把这些范围用一条一条的线段表示。
2.把这些线段的左端点按从小到大的顺序排列，为了尽可能使雷达数少，我们可以遍历一条一条的线段，然后记下当前线段的最小右端点，如果接下来出现的线段的左端点比该最小右端点大，则加一个雷达。
3.还需要注意点的坐标可以为小数。
注意：
1、min(current,arr[i].right) 取最小
2、结构体的left right是经过转化后的，是覆盖的坐标范围，不是输入的x y 。经过输入的x,y 再进行转化为left right
代码实现：
//注意更新的时候，current=min(current,arr[i].right)!!!取min
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int MAXN=1010;
struct Interval
{
double left;//坐标可能是小数
double right;
};
bool compare(Interval x,Interval y)
{
return x.left<y.left;
}
int main()
{
Interval arr[MAXN];
int n,d;
int casenumber=0;
while(scanf("%d%d",&n,&d)!=EOF)
{
bool flag=true;
if( n==0 && d==0)
break;
for(int i=0;i<n;i++)
{
int x,y;
cin>>x>>y;
if(y>d)//相离 无论如何安装，固定d后，均不能覆盖到岛屿
{flag=false;}
else
{
arr[i].left=x-sqrt(d*d*1.0-y*y);
arr[i].right=x+sqrt(d*d*1.0-y*y);
}
//输入结束
//根据分析，按照雷达的左端点按照从小到大排序
}
if(flag==false)
printf("Case %d: %d\n",++casenumber,-1);
else
{
sort(arr,arr+n,compare);//升序
double current_location=arr[0].right;//因为是按照左端从小到大排列，为了涉及范围更大，把第一个雷达安装在第一个岛屿设计范围的右端点处
int answer=1;
for(int i=1;i<n;i++)
{
if(arr[i].left<=current_location)
{
current_location=min(current_location,arr[i].right);
//为什么要取最小的右端点？？min！！！！！！！！！！！！
//
}else
{
answer++;
current_location=arr[i].right;
}
}
printf("Case %d: %d\n",++casenumber,answer);
}
}
return 0;
}
