题目链接：http://poj.org/problem?id=1328
贪心。
看了几个解题报告都说是水题，解题方法也很简单，但是不明白为什么。。。
网上好多代码提交都是wa的，真心醉了……
对于每个小岛，在海岸上有一个区间可以覆盖它。把区间的按左边界排序，然后从左到右扫一遍，记录一个值temp为当前区间的右边界，如果下一个区间的左边界大于temp，结果加一，更新到下一个点，如果下一个区间的右边界都小于temp，令temp等于下一个区间右边界。
AC代码
/********************************************
Problem: 1328 User:
Memory: 688K Time: 16MS
Language: G++ Result: Accepted
*********************************************/
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <math.h>
using namespace std;
const int N = 1005;
int n, d;
struct point {
double x, y;
bool operator < (const point a) const
{
return x < a.x;
}
} p[N];
int solve()
{
int i;
sort(p, p + n);
// for (i = 0; i < n; ++i) {
// printf("%d:%f,%f
", i, p[i].x, p[i].y);
// }
int ans = 1;
double temp = p[0].y;
for (i = 1; i < n; ++i) {
if (p[i].x > temp) {
++ans;
temp = p[i].y;
} else if (p[i].y < temp) {
temp = p[i].y;
}
}
return ans;
}
int main()
{
int i, j = 1;
while (scanf("%d%d", &n, &d) != EOF) {
if (n == 0 && d == 0) break;
int flag = 0;
int x, y;
for (i = 0; i < n; ++i) {
scanf("%d%d", &x, &y);
if (y > d) flag = 1;
p[i].x = x - sqrt((double)d * d - y * y);
p[i].y = x + sqrt((double)d * d - y * y);
}
printf("Case %d: %d
", j++, flag ? -1 : solve());
}
return 0;
}
在 Discuss区找到了一份大神大数据：
2 5 -3 4 -6 3 4 5 -5 3 -3 5 2 3 3 3 20 8 -20 7 -18 6 -5 8 -21 8 -15 7 -17 5 -1 5 -2 3 -9 6 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 7 9 6 10 5 0 0 2 3 0 2 2 3 2 3 0 2 1 3 3 3 1 2 -3 2 2 4 8 5 2 4 -4 4 -3 3 -3 1 -3 0 -1 0 0 5 6 0 3 0 1 2 -3 1 2 1 3 2 1 2 -3 1 2 1 1 2 0 2 2 3 0 2 2 3 4 -5 4 3 4 3 2 3 6 -9 3 -3 1 2 -3 2 2 1 6 2 1 2 1 2 1 2 -3 1 2 1 0 0 1 2 0 2 2 3 0 2 1 3 3 10 1 10 2 3 4 5 3 5 1 10 2 3 4 5 4 7 1 10 2 3 4 5 0 0 3 9 1 10 2 3 4 5 0 0 ================结果 Case 1: 1 Case 2: 2 Case 3: 4 Case 4: 1 Case 5: 1 Case 6: -1 Case 7: 3 Case 8: -1 Case 9: 2 Case 10: 1 Case 11: 1 Case 12: -1 Case 13: -1 Case 14: 2 Case 15: 1 Case 16: 1 Case 17: 1 Case 18: -1 Case 19: -1 Case 20: -1