http://poj.org/problem?id=1328
经典贪心问题。
首先题目要求岸边的雷达要覆盖海中的岛屿,什么情况下岛屿才会被覆盖呢?
也就是要修建的雷达到岛屿的距离小于雷达的覆盖半径,这样就会想到以岛屿为
圆心做圆,与岸边的交点就是可以覆盖这个岛屿的雷达的修建区间,我们确定好
每个岛屿的雷达修建区间后,对这些区间从小到大排序,比较一下就可以了,要
注意被覆盖的区间。
#include <stdio.h> #include <stdlib.h> #include <math.h> struct node { double l,r; }p[1005]; int cmp(const void *a,const void *b) { return (*(node *)a).l>=(*(node *)b).l?1:-1; } int main() { int n,d,x,y,ok,i,cnt = 1,ans; //freopen("in.txt","r",stdin); while(scanf("%d %d",&n,&d) == 2) { if(!n && !d) break; ok = 1; for(i = 0;i < n;i ++) { scanf("%d %d",&x,&y); if(d >= y && ok) { p[i].l=x - sqrt((double)(d*d - y*y)); p[i].r=x + sqrt((double)(d*d - y*y)); } else ok = 0; } printf("Case %d: ",cnt++); if(!ok) printf("-1\n"); else { ans = 1; qsort(p,n,sizeof(node),cmp); double tmp = p[0].r; for(i = 1;i < n;i ++) { if(tmp < p[i].l) { ans ++; tmp = p[i].r; } if(tmp > p[i].r) tmp = p[i].r; } printf("%d\n",ans); } } return 0; }