一本通 1.1 例 3【喷水装置】

首先这道题不是用中心点 $+$ 半径作为一个区间的，可以发现如果那样算的话，圆与圆之间可能还会有一个缝隙，所以应该用勾股定理求出每一个圆所覆盖的区间，注意一下上下的距离够不够，然后就是区间覆盖问题，直接贪心即可。$O(n$²$)$

 1 #include <bits/stdc++.h>
 2 #define INF 0x3f3f3f3f
 3 using namespace std;
 4 int T, n, l, w, num;
 5 struct Str {double l, r;}stu[15010];
 6 int cmp(Str a, Str b) {return a.l == b.l ? a.r > b.r : a.l < b.l;}
 7 double cal(int R) {return (double)sqrt(R * R * 1.0 - w * w * 1.0 / 4);}
 8 int main()
 9 {
10     scanf("%d", &T);
11     while(T--)
12     {
13         num = 0;
14         scanf("%d %d %d", &n, &l, &w);
15         for(int i = 1, x, R; i <= n; ++i)
16         {
17             scanf("%d %d", &x, &R); if(2 * R < w) continue;
18             stu[++num].l = x * 1.0 - cal(R), stu[num].r = x * 1.0 + cal(R);
19             if(stu[num].l < 0) stu[num].l = 0; if(stu[num].r > l) stu[num].r = l;
20         }
21         sort(stu + 1, stu + num + 1, cmp); if(stu[1].l > 0) {puts("-1"); continue;}
22         double end = 0; int ans = 0;
23         for(int i = 0; ; ++ans)
24         {
25             if(end >= l) break; 
26             int change = 0; double maxe = end;//注意这里maxe是double!
27             for(int j = i + 1; j <= num; ++j)
28             {
29                 if(stu[j].l > end) break;
30                 if(stu[j].r > maxe) maxe = stu[j].r, i = j, change = 1; 
31             }
32             end = maxe; 
33             if(!change) break;
34         }
35         if(end < l) puts("-1"); else printf("%d
", ans);
36     }
37     return 0;
38 }