UVA 12097 Pie（二分答案）

题目链接：

这道题虽然不是一道典型的二分答案题，但同样也可以用二分答案来做。

来二分面积为$area$的派，然后看看条件是否矛盾。

与其矛盾的便是$f+1$个人是否每个人都会有。

一个半径为$r$的派只能切出$floor(pi r^2/x)$块。

AC代码：

#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;

const double PI=acos(-1.0);
const int maxn=10005;

int n,f;
double A[maxn];

bool ok(double area){
    int sum=0;
    for(int i=0;i<n;i++) sum+=floor(A[i]/area);
    return sum>=f+1;
}

int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&f);
        double maxa=-1;
        for(int i=0;i<n;i++){
            int r; scanf("%d",&r);
            A[i]=PI*r*r;
            maxa=max(maxa,A[i]); 
        }
        double L=0,R=maxa;
        while(R-L>0.00001){
            double M=(L+R)/2;
            if(ok(M)) L=M; else R=M;
        }
        printf("%.4lf
",L);
    }
    return 0;
}