撒水

Problem Description

大夏天又来了，草坪的小草都被晒枯萎了，LOL（人名）希望买些撒水的装置放在草坪上，LOL的草坪是个长方形，长为w米，宽为h米，要在中线上不同的位置放置喷洒半径为Ri的喷水装置，这样就能喷洒直径为2*Ri(0<Ri<15)的圆，LOL手里有充足的装置x（1<x<10000)个，由于位置是固定了，所以不一定能喷洒整个草坪，如果可以的话他希望用最少的装置来喷洒整个草坪，10个以内自己能搞定，多了就糊涂了，所以请你这个ACMer来帮他完成。

Input

第一行输入一个正整数N（1 <= 20 ）表示共有n次测试数据。
每一组测试数据的第一行有三个整数n, w, h，n表示共有n个喷水装置，w为草坪长度，h为草坪宽度。
接下来的n行，都有两个整数x 和r ,x表示第i个喷水装置的的横坐标（最左边为0），r表示该喷水装置能喷洒的圆的半径.

Output

每组测试数据输出一个正整数，表示共需要多少个喷水装置。
如果不存在一种能够把整个草坪湿润的方案，请输出0。

Sample Input

Sample Output

1
2

解释：

之前做过一个类似的题目，所以知道解决的办法。以前好像是一个卫星有关的题目，从想要覆盖整个X轴，要求最下的卫星数。这个题目很像。

首先每一个洒水器画一个圆，如果这个洒水不能喷到草坪的上边，那么这个洒水就肯定是没有用的。如果可以喷到上边，就会有一个截距，有两个交点(lx, rx)。因此对于每一个洒水器，我按照lx，最小的优先，lx相等的时候，rx最大优先排序。首先判断最小的一个lx 是不是小于0，最大一个rx是不是大于w. 然后对于长边的每一个点，判断是不是有洒水器可以覆盖。如果有一个不满足，直接输出0.

 1 #include<bits/stdc++.h>
 2 
 3 using namespace std;
 4 
 5 const int N = 10001;
 6 
 7 struct spray{
 8   double lx, rx;
 9 };
10 
11 struct spray sprays[N];
12 
13 int cmp(spray a, spray b) {
14   if (abs(a.lx - b.lx) < 0.00001) {
15     return a.rx > b.rx;
16   } else {
17     return a.lx < b.lx;
18   }
19 }
20 
21 
22 int main() {
23   int t;
24   scanf("%d", &t);
25   while (t--) {
26     int n, s = 0;
27     double w, h;
28     scanf("%d %lf %lf", &n, &w, &h);
29     double x, r;
30     for (int i = 0; i < n; i++) {
31       scanf("%lf %lf", &x, &r);
32       if (r >= h/2) {
33          sprays[s].lx = double(x - sqrt(r * r - (h / 2) * (h / 2)));
34          sprays[s].rx = double(x + sqrt(r * r - (h / 2) * (h / 2)));
35          s++;
36       }
37      
38     }
39     sort(sprays, sprays+s, cmp);
40     double lx = 0, rx = 0.0;
41    
42     if (sprays[0].lx > 0.0 || sprays[s-1].rx < w || s == 0) printf("0
");
43     else {
44       int sums = 0, i = 0; 
45       double max_rx = 0;
46       while (rx < w && i < s) {
47         max_rx = 0;
48         while (sprays[i].lx <= rx && i < s && max_rx < w) {
49           if (max_rx <= sprays[i].rx) {
50             max_rx = sprays[i].rx;
51           }
52           i++;
53         }
54         if (abs(max_rx - 0) < 0.00001) {
55           sums = 0;
56           break;
57         }
58         rx  = max_rx;
59         sums++;
60       }
61       printf("%d
", sums);
62     }
63   }
64   return 0;
65 }

View Code

这个图画的，很阳光，很帅气。（其实chou的一批）