UVALive 2519 Radar Installation 雷达扫描 区间选点问题

题意：在坐标轴中给出n个岛屿的坐标，以及雷达的扫描距离，要求在y=0线上放尽量少的雷达能够覆盖全部岛屿。

很明显的区间选点问题。

代码：

/**  Author:      illuz <iilluzen[at]gmail.com>*  Blog:        http://blog.csdn.net/hcbbt*  File:        l2911.cpp*  Create Date: 2013-09-09 20:51:05*  Descripton:   */#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>using namespace std;const int MAXN = 1010;int n, r, cas = 1;struct Point {double lhs, rhs;} a[MAXN];bool cmp(Point a, Point b) {if (a.rhs != b.rhs)return a.rhs < b.rhs;return a.lhs > b.lhs;}int main() {int x, y;bool flag;while (scanf("%d%d", &n, &r) && (n || r)) {flag = true;memset(a, 0, sizeof(a));for (int i = 0; i < n; i++) {scanf("%d%d", &x, &y);if (flag) {if (y > r) {flag = false;continue;}double t = sqrt((double)r * r - y * y);a[i].lhs = x - t;a[i].rhs = x + t;}}printf("Case %d: ", cas++);if (!flag)printf("-1\n");else {sort(a, a + n, cmp);//for (int i = 0; i < n; i++)//printf("%lf %lf\n", a[i].lhs, a[i].rhs);int ans = 1;double start = a[0].rhs;for (int i = 1; i < n; i++) {if (a[i].lhs - start <= 1e-4)continue;ans++;start = a[i].rhs;}printf("%d\n", ans);}}return 0;}