本文主要是介绍uvalive 2519 - Radar Installation(区间选点问题），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目连接：2519 - Radar Installation
题目大意：给出n和半径r， 然后给出n个坐标， 现在要求在x轴选出最少的点， 以这些点为圆心， 半径为r画圆， 要求将所有点均在画的圆内。
解题思路：区间选点问题，就是变形了一下。
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
using namespace std;
const int N = 1005;struct thing {double l;double r;
}tmp[N];bool cmp(const thing& a, const thing& b) {if (a.r != b.r) return a.r - b.r < 0;else return a.l - b.l > 0;
}int main() {int n, r, x, y, cas = 1;while (scanf("%d%d", &n, &r) == 2 && n + r) {// Init;int flag = 0;double t;memset(tmp, 0, sizeof(tmp));// Read;for (int i = 0; i < n; i++) {scanf("%d%d", &x, &y);if (y > r) {flag = 1;continue;}t = sqrt(r * r - y * y);tmp[i].l = x - t;tmp[i].r = x + t;}printf("Case %d: ", cas++);if (flag)printf("-1\n");else {sort(tmp, tmp + n, cmp);int cnt = 1;double begin = tmp[0].r;for (int i = 1; i < n; i++) {if (tmp[i].l - begin <= 1e-4) continue;cnt++;begin = tmp[i].r;}printf("%d\n", cnt);}}return 0;
}
这篇关于uvalive 2519 - Radar Installation(区间选点问题）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
