SHARE
TWEET

Referência para Pie (LA 3635)

royalsflush Jul 1st, 2012 1 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdio.h>
  2. #include <algorithm>
  3. #include <math.h>
  4. using namespace std;
  5.  
  6. const double eps=1e-12;
  7. double pi;
  8.  
  9. int n,f,_42;
  10. double r[10010];
  11.  
  12. inline int cmp(double a, double b) {
  13.         return (a-b>eps? 1 : (b-a>eps? -1 : 0));
  14. }
  15.  
  16. inline double area(double rad) {
  17.         return rad*rad*pi;
  18. }
  19.  
  20. bool can(double sz) {
  21.         double rem=area(r[0]);
  22.         int fr=0;
  23.  
  24.         for (int i=0; i<n; )
  25.                 if (cmp(rem,sz)>=0)
  26.                         rem-=sz, fr++;
  27.                 else
  28.                         rem=area(r[++i]);
  29.  
  30.         return fr>=f+1;
  31. }
  32.  
  33. int main() {
  34.         pi = acos(-1.0);
  35.         scanf("%d", &_42);
  36.  
  37.         while (_42--) {
  38.                 scanf("%d %d", &n,&f);
  39.                
  40.                 for (int i=0; i<n; i++)
  41.                         scanf("%lf" ,&r[i]);
  42.  
  43.                 double beg=0, end=area(*max_element(r,r+n));
  44.  
  45.                 for (int i=0; i<50; i++) {
  46.                         double mid=(beg+end)/2.0;
  47.  
  48.                         if (can(mid)) beg=mid;
  49.                         else end=mid;
  50.                 }
  51.  
  52.                 printf("%.4lf\n", beg);
  53.         }
  54.  
  55.         return 0;
  56. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top