题目大意：长 l 宽 w 的草坪，有 n 个喷洒器，给出喷洒器圆心坐标和半径，问最少用几个喷洒器能保证覆盖所有草坪。 解题思路：需要转换一下 对于任意一个喷洒器，利用半径和宽极坐标求出图中红线的左右两端坐标，就转换为简单的区间覆盖，然后利用贪心思想即可。注意直径小于宽的情况可以直接排除。
#include<iostream> #include<stdio.h> #include<algorithm> #include<cmath> using namespace std; struct line{ double lef, rig; }; int n; double w, l; line li[10000+10]; void f(int cnt, double o, double r){ double tmp = sqrt(r*r-((w*1.0/2.0)*(w*1.0/2.0))); li[cnt].lef = o-tmp; li[cnt].rig = o+tmp; } bool cmp(line a, line b) { return a.lef < b.lef; } int main() { while (scanf("%d%lf%lf", &n, &l, &w) != EOF){ int cnt = 0; for (int i = 0; i < n; i++) { double o, r; scanf("%lf%lf", &o, &r); if (2*r < w) continue; f(cnt++, o, r); } sort(li, li+cnt, cmp); int num = 0; double left = 0, right = 0; bool flag = false; if (li[0].lef <= 0) { int cur = 0; while (cur < cnt) { int i; for (i = cur; i < cnt && li[i].lef <= left; i++) if (li[i].rig > right) right = li[i].rig; if (i == cur) break; num++; left = right; cur = i; if (left >= l) { flag = true; break; } } } if (flag) printf("%d\n", num); else printf("-1\n"); } return 0; }double 和 int 转换这里 WA 了，贪心时左端的判断放在循环里面导致 TLE，应该作为循环条件判断的。emm..太久没写题
