题意：有f+1个人来分N个圆形派，每个人能得到的必须是一整块派，而不是几块拼在一起，且面积要相同，求每个人最多能得到多大面积的派
分析：对于每个人分到的派的大小，其上界是面积最大的派，下界可以取得0，在两者之间用二分的方法做就可以了，二分的判定是，给定一个面积x，每个派能分成[pi*r*r/x]份，看这个结果是否大于f+1
代码
1 #include <stdio.h> 2 #include <iostream> 3 #include <math.h> 4 #include <algorithm> 5 #define zz 6 using namespace std; 7 const double PI = acos(-1.0); 8 const int MAXN = 10000 + 5; 9 10 int n, f; 11 double A[MAXN]; 12 13 bool erfen(double area){ 14 int sum = 0; 15 for(int i=0; i<n; i++) sum+=floor(A[i]/area); 16 return sum>=f+1; 17 } 18 19 double max(double a, double b){ 20 return a>b?a:b; 21 } 22 23 int main(){ 24 #ifndef zz 25 freopen("in.txt", "r", stdin); 26 #endif 27 int cas; 28 scanf("%d", &cas); 29 while(cas--){ 30 scanf("%d%d", &n, &f); 31 double maxa = -1; 32 int i; 33 for(i=0; i<n; i++){ 34 int r; 35 scanf("%d", &r); 36 A[i] = PI*r*r; 37 maxa= max(maxa, A[i]); 38 } 39 double l=0, r=maxa; 40 while(r-l>1e-5){ 41 double m = (l+r)/2; 42 if(erfen(m)) l=m; 43 else r=m; 44 } 45 printf("%.4lf\n", l); 46 } 47 return 0; 48 }
