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-;
int n,f;
const int maxn=1e4+;
double a[maxn];
bool check(double v)
{
int cnt=;
for(int i=;i<n;i++)
{
double size=pi*a[i]*a[i];
cnt+=(int)(size/v);
}
if(cnt>=f+)
{
return true;
}
else
{
return false;
}
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&f);
for(int i=;i<n;i++)
{
scanf("%lf",&a[i]);
}
sort(a,a+n);
double l=0.0;
double r=pi*a[n-]*a[n-];
while(r-l>=eps)
{
double mid=(l+r)/2.0;
if(check(mid))
{
l=mid+eps;
}
else
{
r=mid-eps;
}
}
printf("%.4f\n",l);
}
return ;
}