【二分贪心+精度问题】F. Pie

https://www.bnuoj.com/v3/contest_show.php?cid=9154#problem/F

【题意】

• 给定n个已知半径的披萨，有m个人要分这n个披萨
• 要求每个人分到的面积同样大
• 每个人只能取“一块”披萨上的一部分（或整块披萨），不能从A披萨取一点，再从B披萨取一点

【思路】

• num[v]是非严格单调递减函数，所以可以二分查找答案。v是每人的披萨大小，num是可以满足多少人
• 这道题eps必须是1e-6或1e-7,1e-8会T,1e-5会WA
• 

【Accepted】

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#include<queue>
using namespace std;
const double pi=acos(-1.0);
const double eps=1e-8;
int n,f;
const int maxn=1e4+3;
double a[maxn];
bool check(double v)
{
    int cnt=0;
    for(int i=0;i<n;i++)
    {
        double size=pi*a[i]*a[i];
        cnt+=(int)(size/v);
    }
    if(cnt>=f+1)
    {
        return true;
    }
    else 
    {
        return false;
    }
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&f);
        for(int i=0;i<n;i++)
        {
            scanf("%lf",&a[i]);    
        }
        sort(a,a+n);
        double l=0.0;
        double r=pi*a[n-1]*a[n-1];
        while(r-l>=eps)
        {
            double mid=(l+r)/2.0;
            if(check(mid))
            {
                l=mid+eps;
            }
            else
            {
                r=mid-eps;
            }
        }
        printf("%.4f
",l);
    }
    return 0;
}