http://acm.nyist.net/JudgeOnline/problem.php?pid=12
喷水装置(二)
时间限制:3000 ms | 内存限制:65535 KB
难度:4
- 描述
- 有一块草坪,横向长w,纵向长为h,在它的橫向中心线上不同位置处装有n(n<=10000)个点状的喷水装置,每个喷水装置i喷水的效果是让以它为中心半径为Ri的圆都被润湿。请在给出的喷水装置中选择尽量少的喷水装置,把整个草坪全部润湿。
- 输入
- 第一行输入一个正整数N表示共有n次测试数据。
每一组测试数据的第一行有三个整数n,w,h,n表示共有n个喷水装置,w表示草坪的横向长度,h表示草坪的纵向长度。
随后的n行,都有两个整数xi和ri,xi表示第i个喷水装置的的横坐标(最左边为0),ri表示该喷水装置能覆盖的圆的半径。 - 输出
- 每组测试数据输出一个正整数,表示共需要多少个喷水装置,每个输出单独占一行。
如果不存在一种能够把整个草坪湿润的方案,请输出0。 - 样例输入
2 2 8 6 1 1 4 5 2 10 6 4 5 6 5
- 样例输出
1 2
解题思路:类似于区间覆盖问题,和ZOJ1360比较相似-> http://www.cnblogs.com/angle-qqs/p/4073247.html
1 #include <stdio.h>
2 #include <string.h>
3 #include <stdlib.h>
4 #include <math.h>
5
6 struct P{
7 double x;
8 double left, right;
9 }p[1010];
10
11 int cmp(const void *a, const void *b){
12 struct P *c = (struct P *)a;
13 struct P *d = (struct P *)b;
14 return c->left > d->left ? 1 : -1;
15 }
16
17 int main(){
18 int T, n, w, h, i, ans, flag;
19 double r, dis, h1, sum, max;
20 scanf("%d", &T);
21 while(T--){
22 scanf("%d %d %d", &n, &w, &h);
23 h1 = 1.0 * h / 2.0;
24 for(i = 0; i < n; i++){
25 scanf("%lf %lf", &p[i].x, &r);
26 if(r > h1){//当半径大于高的一半的时候
27 dis = sqrt((r * r) - (h1) * (h1));
28 p[i].left = p[i].x - dis;
29 p[i].right = p[i].x + dis;
30 }
31 else{
32 p[i].left = p[i].right = p[i].x;
33 }
34
35 }
36 qsort(p, n, sizeof(p[0]), cmp);
37 // for(i = 0; i < n; i++){
38 // printf("%lf %lf ", p[i].left, p[i].right);
39 // }
40 sum = 0;
41 ans = 0;
42 flag = 0;
43 while(sum < w){//当覆盖长度小于宽的时候
44 max = 0;
45 for(i = 0; i < n && p[i].left <= sum; i++){//求当前最多覆盖
46 if(p[i].right - sum > max){
47 max = p[i].right - sum;
48 }
49 }
50 if((max - 0) < 1e-9){//如果不能连续覆盖
51 flag = 1;
52 break;
53 }
54 else{
55 sum += max;
56 ans++;
57 }
58 }
59 if(flag == 1){
60 printf("0 ");
61 }
62 else{
63 printf("%d ", ans);
64 }
65 }
66 return 0;
2 #include <string.h>
3 #include <stdlib.h>
4 #include <math.h>
5
6 struct P{
7 double x;
8 double left, right;
9 }p[1010];
10
11 int cmp(const void *a, const void *b){
12 struct P *c = (struct P *)a;
13 struct P *d = (struct P *)b;
14 return c->left > d->left ? 1 : -1;
15 }
16
17 int main(){
18 int T, n, w, h, i, ans, flag;
19 double r, dis, h1, sum, max;
20 scanf("%d", &T);
21 while(T--){
22 scanf("%d %d %d", &n, &w, &h);
23 h1 = 1.0 * h / 2.0;
24 for(i = 0; i < n; i++){
25 scanf("%lf %lf", &p[i].x, &r);
26 if(r > h1){//当半径大于高的一半的时候
27 dis = sqrt((r * r) - (h1) * (h1));
28 p[i].left = p[i].x - dis;
29 p[i].right = p[i].x + dis;
30 }
31 else{
32 p[i].left = p[i].right = p[i].x;
33 }
34
35 }
36 qsort(p, n, sizeof(p[0]), cmp);
37 // for(i = 0; i < n; i++){
38 // printf("%lf %lf ", p[i].left, p[i].right);
39 // }
40 sum = 0;
41 ans = 0;
42 flag = 0;
43 while(sum < w){//当覆盖长度小于宽的时候
44 max = 0;
45 for(i = 0; i < n && p[i].left <= sum; i++){//求当前最多覆盖
46 if(p[i].right - sum > max){
47 max = p[i].right - sum;
48 }
49 }
50 if((max - 0) < 1e-9){//如果不能连续覆盖
51 flag = 1;
52 break;
53 }
54 else{
55 sum += max;
56 ans++;
57 }
58 }
59 if(flag == 1){
60 printf("0 ");
61 }
62 else{
63 printf("%d ", ans);
64 }
65 }
66 return 0;
67 }