题目地址：http://poj.org/problem?id=1328
1 /* 2 贪心 3 (转载)题意：有一条海岸线，在海岸线上方是大海，海中有一些岛屿， 4 这些岛的位置已知，海岸线上有雷达，雷达的覆盖半径知道， 5 问最少需要多少个雷达覆盖所有的岛屿。 6 (错误)思路：我开始是想从最左边的点雷达能探测的到的最右的位置出发，判断右边其余的点是否与该点距离小于d 7 是，岛屿数-1；不是，雷达数+1，继续。。。 8 (正确)思路：每个岛屿的座标已知，以雷达半径为半径画圆，与x轴有两个交点。 9 也就是说，若要覆盖该岛，雷达的位置范围是这两个交点。因此转化为覆盖区间的问题。 10 参考代码：http://www.cnblogs.com/kuangbin/archive/2011/07/30/2121838.html 11 */ 12 #include13 #include 14 #include 15 #include 16 #include 17 #include 18 using namespace std; 19 20 const int MAXN = 1e3 + 10; 21 const int INF = 0x3f3f3f3f; 22 struct NODE 23 { 24 int x, y; 25 double l, r; 26 }node[MAXN]; 27 28 bool cmp(NODE a, NODE b) 29 { 30 return a.l < b.l; 31 } 32 33 bool ok(int n, int d) 34 { 35 if (d < 0) return false; 36 for (int i=1; i<=n; ++i) 37 { 38 if (node[i].y > d) return false; 39 } 40 41 return true; 42 } 43 44 void work(int n, int d) 45 { 46 int cnt = 1; 47 double now = node[1].r; 48 for (int i=2; i<=n; ++i) 49 { 50 if (now > node[i].r) now = node[i].r; 51 if (now < node[i].l) 52 { 53 now = node[i].r; 54 cnt++; 55 } 56 } 57 printf ("%d\n", cnt); 58 } 59 60 int main(void) //POJ 1328 Radar Installation 61 { 62 //freopen ("I.in", "r", stdin); 63 64 int n, d; 65 int cnt = 0; 66 while (~scanf ("%d%d", &n, &d) && n && d) 67 { 68 for (int i=1; i<=n; ++i) 69 { 70 scanf ("%d%d", &node[i].x, &node[i].y); 71 node[i].l = (double)node[i].x - sqrt ((double)d * d - node[i].y * node[i].y); 72 node[i].r = (double)node[i].x + sqrt ((double)d * d - node[i].y * node[i].y); 73 } 74 sort (node+1, node+1+n, cmp); 75 printf ("Case %d: ", ++cnt); 76 if (!ok (n, d)) 77 { 78 printf ("%d\n", -1); continue; 79 } 80 work (n, d); 81 } 82 83 return 0; 84 } 85 86 /* 87 void work(int n, int d) 88 { 89 int i = 1; 90 int j = 1; 91 int next = 1; 92 int num = 0; 93 int cnt = 0; 94 while (num < n) 95 { 96 double res = node[i].x + sqrt (d * d - node[i].y * node[i].y); 97 cnt++; num++; 98 int flag = 0; 99 fors (j=i+1; j<=n; ++j)100 {101 if (pow (node[j].x - res, 2) + pow (node[j].y, 2) <= d * d)102 {103 num++; next = j; flag = 1;104 }105 }106 if (flag) i = next + 1;107 else i++;108 }109 printf ("%d\n", cnt);110 }111 */