1.POJ-1328 Radar Installation
题意：给出一定数量的岛屿和雷达的观测范围d,问在海岸线最少建设多少个雷达就能覆盖完所有的岛屿。
这是一道区间选点的问题，我思路错了
给定多个区间，区间之间可能会发生部分重叠，一个区间内只要选中一个点，这个区间就成了被选中区间，
问： 要使所有区间都成为被选中区间，最少需要几个点？
再回看这个问题，就是一个标准的问题。每个岛都有一个雷达区间，问找最少几个雷达，能使所有区间都选中。
题目分析：
要想使雷达最少，每个雷达就要尽可能多的覆盖岛屿。我最开始的思路一直是从最左边未被覆盖的岛屿的x坐标开始，
在[x,x+sqrt(d^2 - y^2)]之间选择覆盖最多的x坐标建立一个雷达，并消去被覆盖的岛屿，复杂度太高，而且感觉像模拟，没有抓住贪心题的精髓。
新思路：
可以转换一下对象，原来一直是找最优的点建立雷达，都是对雷达考虑的。现在对岛屿考虑。我们可以将雷达能覆盖到这个岛屿的左右范围求出来,
并对范围进行排序，从左到右，拥有交集范围的一堆岛屿就可以用一个雷达监测。问题就变成了有几堆这样的岛屿（拥有一个公共交点）
解：
求出各岛屿的左右l,r，排序,按照区间右侧由小到大排序；
初始点为第一个区间的右侧(tx);
遍历
如果tx在区间内，continue
否则，更新tx,sum++;
注意
某岛屿y>d，输出-1
d<=0 输出-1
输出格式
取double
代码：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#define x first
#define y second
using namespace std;
const int MA=1e5+5;
typedef pair<double,double> pd;
pd a[MA];
pd b[MA];
bool cmp(pd z1,pd z2){
if(z1.y==z2.y)return z1.x<z2.x;
else return z1.y<z2.y;
}
int main(){
int n,d;
bool flag;
int t=1;
while(scanf("%d %d",&n,&d)){
if(n==0&&d==0)break;
flag=true;
if(d<=0)flag=false;
for(int i=0;i<n;i++){
scanf("%lf %lf",&a[i].x,&a[i].y);
if(a[i].y>d)flag=false;
b[i].x=a[i].x-sqrt(d*d-a[i].y*a[i].y);
b[i].y=a[i].x+sqrt(d*d-a[i].y*a[i].y);
}
sort(b,b+n,cmp);
int sum=1;
double tx=b[0].y;
for(int i=0;i<n;i++){
if(tx>=b[i].x&tx<=b[i].y)continue;
else{
tx=b[i].y;
sum++;
}
}
if(flag)cout<<"Case "<<t<<": "<<sum<<endl;
else cout<<"Case "<<t<<": -1"<<endl;
t++;
}
return 0;
}