喷水 1

6-喷水装置（一）

内存限制:64MB 时间限制:3000ms 特判: No
通过数:260 提交数:473 难度:3

题目描述:

现有一块草坪，长为20米，宽为2米，要在横中心线上放置半径为Ri的喷水装置，每个喷水装置的效果都会让以它为中心的半径为实数Ri(0<Ri<15)的圆被湿润，这有充足的喷水装置i（1<i<600)个，并且一定能把草坪全部湿润，你要做的是：选择尽量少的喷水装置，把整个草坪的全部湿润。

输入描述:

第一行m表示有m组测试数据
每一组测试数据的第一行有一个整数数n，n表示共有n个喷水装置，随后的一行，有n个实数ri，ri表示该喷水装置能覆盖的圆的半径。

输出描述:

输出所用装置的个数

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <string>
 5 #include <algorithm>
 6 #include <utility>
 7 #include <vector>
 8 #include <map>
 9 #include <queue>
10 #include <stack>
11 #include <cstdlib>
12 #include <cmath>
13 typedef long long ll;
14 #define lowbit(x) (x&(-x))
15 #define ls l,m,rt<<1
16 #define rs m+1,r,rt<<1|1
17 using namespace std;
18 #define pi acos(-1)
19 #define P pair<ll,ll>
20 const int N  = 2e6+200;
21 const ll mod= 1000000007;
22 double cmp(double x,double y){
23     return x>y;
24 }
25 int t,n;
26 double r[1000];
27 int main()
28 {
29     scanf("%d",&t);
30     while(t--){
31         scanf("%d",&n);
32         for(int i=0;i<n;i++) scanf("%lf",&r[i]);
33         sort(r,r+n,cmp);
34         double ans=20.0;
35         int cnt = 0;
36         for(int i=0;i<n;i++){
37             double x = 2.0*sqrt(r[i]*r[i]-1);//圆和长相交的距离
38             ans-=x;
39             cnt++;
40             if(ans<=0) break;//达到20即可
41         }
42         printf("%d
",cnt);
43     }
44     return 0;
45 }

12-喷水装置（二）


内存限制:64MB
                        时间限制:3000ms
                        特判: No 
                    
通过数:123
                        提交数:420
                        难度: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。

样例输入:

样例输出:

1
2

提示:

没有提示哦

来源:

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <string>
 5 #include <algorithm>
 6 #include <utility>
 7 #include <vector>
 8 #include <map>
 9 #include <queue>
10 #include <stack>
11 #include <cstdlib>
12 #include <cmath>
13 typedef long long ll;
14 #define lowbit(x) (x&(-x))
15 #define ls l,m,rt<<1
16 #define rs m+1,r,rt<<1|1
17 using namespace std;
18 #define pi acos(-1)
19 #define P pair<double,double>
20 const int N  = 1e4+200;
21 const ll mod= 1000000007;
22 int n,t;
23 double w,h;
24 double o[N],r[N];
25 //转化为喷水装置一就可以了 
26 int main()
27 {
28     scanf("%d",&t);
29     while(t--)
30     {
31         scanf("%d%lf%lf",&n,&w,&h);
32         double hh = h/2;
33         priority_queue<P,vector<P>,greater<P> >Q; 
34         for(int i =0;i<n;i++)
35         {
36             scanf("%lf%lf",&o[i],&r[i]);
37             if(r[i]>=hh){
38                 double m = sqrt(r[i]*r[i]-hh*hh);
39                 double x = o[i]-m,y=o[i]+m;
40                 Q.push(P(x,y));
41                 //printf("%.2f %.2f
",x,y);
42             }
43         }
44         int  flag=1,cnt=0;
45         double en =0.0;
46         while(en<w&&flag){
47             flag =0;
48             double st=en;
49             while(!Q.empty()&&Q.top().first<=st){
50                 P p =Q.top();
51                 double u = p.second;
52                 Q.pop();
53                 if(u>en){
54                     en = u;
55                     flag=1;
56                 }
57             }
58             cnt++;
59         }
60         if(flag) printf("%d
",cnt);
61         else {
62             printf("0
");
63         }
64      } 
65      return 0;
66 }