6-喷水装置（一）

内存限制:64MB 时间限制:3000ms 特判: No

通过数:68 提交数:111 难度:3

题目描述:

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

输入描述:

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

输出描述:

输出所用装置的个数

样例输入:

252 3.2 4 4.5 6 101 2 3 1 2 1.2 3 1.1 1 2

样例输出:

思路

因为要求最少的喷水装置，所以把装置的半径从大到小拍一下序，然后利用一点几何的知识，求出圆与草坪的边界相交的长度，直到草坪完全被喷水装置覆盖，停止

AC代码

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #define ll long long#define ull unsigned long long#define ms(a,b) memset(a,b,sizeof(a))#define pi acos(-1.0)#define INF 0x7f7f7f7f#define lson o<<1#define rson o<<1|1#define bug cout<<"---------"<
                 
                  b;}int main(int argc, char const *argv[]){ ios::sync_with_stdio(false); #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); double _begin_time = clock(); #endif int t; int n; cin>>t; while(t--) { double s=20.0; cin>>n; for(int i=0;i
                  
                   >a[i]; sort(a,a+n,cmp); int ans=0; for(int i=0;i

转载于:https://www.cnblogs.com/Friends-A/p/10324339.html

你可能感兴趣的文章

图标字体的使用(fontello.com)字体推荐及使用技巧