fork download 
  1. //poj3122 Pie 
  2. //binary sreach
  3.  
  4. #include <stdio.h>
  5. #include <math.h>
  6.  
  7. const double PI = acos(-1.0);
  8. const int maxn = 10000 + 5;
  9. double a[maxn];
  10. int n, f;
  11. const double eps = 1e-5;
  12. bool check(double x)
  13. {
  14.     int cnt = 0;
  15.     for(int i=0; i<n; ++i)
  16.     {
  17.       cnt += floor(a[i]/x);
  18.     }
  19.     return  cnt >= f+1;
  20. }
  21.  
  22. int main()
  23. {
  24.     int T, i, x;
  25.     scanf("%d",&T);
  26.     while(T--)
  27.     {
  28.         scanf("%d%d",&n,&f);
  29.         double maxv = -1;
  30.         for(i=0; i<n; ++i)
  31.         {
  32.             scanf("%d",&x);
  33.             a[i] = PI*x*x;
  34.             if(maxv < a[i]) maxv = a[i];
  35.         }
  36.         double l = 0, r = maxv, m;
  37.         while(r-l > eps) 
  38.         //for(int i=0; i<100; ++i) ，这样写也能保证精度
  39.         {
  40.             m = (l + r)/2;
  41.             if( check(m) ) l = m;
  42.             else r = m;
  43.         }
  44.         printf("%.4f\n",m);
  45.     }
  46.     return 0;
  47. }
Success #stdin #stdout 0s 3376KB
comments (?)
stdin 
3
3 3
4 3 3
1 24
5
10 5
1 4 2 3 4 5 6 5 4 2
stdout 
25.1327
3.1416
50.2655
https://ideone.com/6q8zc4
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!