本文主要是介绍uva10382 - Watering Grass（区间覆盖变形），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目：uva10382 - Watering Grass（区间覆盖变形）
题目大意：要给一片草坪浇水，给定草坪的长度和宽度，给出每个喷头的圆心C和喷水的半径R，问最少要几个喷头可以给整片草坪都浇上水。
解题思路：区间覆盖问题的变形，因为草坪有宽度W，所以这个每个喷头的有效范围是[C- sqrt（R* R - 0.25 * W * W , C + sqrt (R*R - 0.25 * W *W)].
代码：
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <math.h>
using namespace std;
const int N = 10010;struct Seg {double x;double y;friend bool operator < (const Seg&a,const Seg&b){ return a.x < b.x; }
}seg[N];
int n;
double order, h;void input() {int sum = 0;double r, p;for (int i = 0; i < n; i++) {scanf("%lf%lf", &p, &r);if (h / 2 >= r) continue;double q = sqrt(r * r - h * h / 4.0);seg[sum].x = p - q;seg[sum].y = p + q;sum++;}n = sum;
}int main() {while (scanf("%d%lf%lf", &n, &order, &h) == 3) {memset(seg, 0, sizeof(seg));input();sort(seg, seg + n);int cnt = 0;double begin = 0, over = 0;bool flag = false;if (seg[0].x <= 0) {int i = 0;while (i < n) {int j = i;while (j < n && begin >= seg[j].x) {if (seg[j].y > over)over = seg[j].y;j++;}if (i == j) break;cnt++;begin = over;i = j;if (begin >= order) {flag = true;break;}}}if (flag)printf("%d\n", cnt);elseprintf("-1\n");}return 0;
}
这篇关于uva10382 - Watering Grass（区间覆盖变形）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
