poj1328解题报告
1.算法
本题是一道贪心题，和《算法艺术与信息学竞赛》中的“照亮的山景”题极为相似。
(1)首先我们求出在每个岛屿放雷达以后在x轴上所能覆盖的区间，是在x轴的上的一个线段，即在这一段上放置雷达可以覆盖到该岛。
(2)我们把每个岛对应的线段找出来，只要在这些线段上放置一些雷达，使得所有的线段上都有雷达即可符合题意（注意如果半径为0或者坐标的y轴小于半径的话将无法完成覆盖，输出-1）。
(3)我们将线段根据左端点排序，找出如果一个线段包含另一个线段，则可以忽略外面的那一个线段（道理很简单），将其设为无效。
(4)在剩下的线段中从左往右遍历，对于每个线段，尽量选取该线段的最右边的点作为雷达，如果之前有雷达在该线段上，则跳过该线段。
(5)每次加一个雷达将计数器加一，最后可以得到解。
2.实现
(1)特别注意对于-1情况的判断，注意如果半径为0或者坐标的y轴小于半径的话将无法完成覆盖。
(2)边读边判断的时候要确保改组所有的数据都读完才能输出-1继续下一组的处理。
(3)在判断x轴上线段是否因为包含其他线段而无效时，可以从右往左遍历从而一次遍历完成判断。
(4)在放置雷达时需要从左往右遍历，这里需要设置一个很小的doule值，以方便第一个雷达的选取，这个值要比integer的最小值的两倍还要小一点，故设为-5000000000。

3.代码

Problem: 1328User: godfrey90Memory: 368KTime: 79MSLanguage: G++Result: Accepted#include <cstdio>#include <cmath>struct unit {double h;double t;bool able;};void work(int id,int m, int n);bool get_ht(int r,int x,int y,double *ph,double *pt);int main() {int m, n;int id=0;scanf("%d %d", &m, &n);while (!((m == 0) && (n == 0))) {work(id++,m, n);scanf("%d %d", &m, &n);}return 1;}void work(int id,int m, int n) {//initint x,y;unit arr[1000];int p = 0;bool flag = true;for (int i = 0; i < m; i++) {scanf("%d %d", &x, &y);if(!get_ht(n,x,y,&(arr[i].h),&(arr[i].t)))flag = false;arr[p++].able = true;}if(!flag){printf("Case %d: -1\n",id+1);return;}//sortint len = p;for (int i = 0; i < len; i++) {for (int j = i + 1; j < len; j++) {if (arr[i].h > arr[j].h) {unit temp = arr[i];arr[i] = arr[j];arr[j] = temp;}}}//disable the useless oneint tail = arr[len - 1].t;for (int i = len - 2; i >= 0; i--) {if (arr[i].t >= tail) {arr[i].able = false;} else {tail = arr[i].t;}}//find the radarint count = 0;double last = -5000000000;for (int i = 0; i < len; i++) {if ((arr[i].able) && (arr[i].h > last)) {count++;last = arr[i].t;}}printf("Case %d: %d\n",id+1,count);}bool get_ht(int r,int x,int y,double *ph,double *pt){if((r<0)||(r*r-y*y<0)) return false;double dlt = sqrt(r*r-y*y);*ph = x-dlt;*pt = x+dlt;return true;}