https://vjudge.net/problem/POJ-1328
贪心策略选错了恐怕就完了吧。。
一开始单纯地把island排序，然后想从左到右不断更新，其实这是错的。。。因为空中是个圆弧。
后来知道了通过对每个island求雷达范围，将这些范围排序，但是去重策略也没想对。因为有两种情况，都需要更新t值，但是只有一种需要ans++。
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<set>
#define INF 0x3f3f3f3f
typedef long long ll;
using namespace std;
typedef struct{
double x, y;
}Node;
Node node[];
double lengthb(int c, int a)
{
return sqrt(c*c-a*a);
}
bool cmp(const Node a, const Node b)
{
return a.x<b.x;
}
int main()
{
int n, d, a, b, kase=;
while(cin >> n >> d){
if(!n&&!d) break;
int flag=;
for(int i = ; i < n; i++){
cin >> a >> b;
if(d < b) flag=;
else{
double tmp = lengthb(d, b);
node[i].x = a-tmp, node[i].y = a+tmp;
}
}
cout << "Case " << ++kase << ": ";
if(!flag){
cout << "-1" << endl;
continue;
}
sort(node, node+n, cmp);
double t = node[].y;
int ans = ;
for(int i = ; i < n; i++){
if(node[i].y<t||abs(node[i].y-t)<1e-){//这种情况不用ans++,但该雷达的检测范围却因此缩小了
t = node[i].y;
}
else if(t<node[i].x){
t = node[i].y;
ans++;
}
}
cout << ans << endl;
}
return ;
}