这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。
传送门:
http://acm.hdu.edu.cn/showproblem.php?pid=1969
分析:二分搜索
代码:
#include
#include
#include
using namespace std;
double pie[10005];
int T, N, F;
double PI = acos(-1.0);
bool test(double x)
{
int cnt = 0;
for(int i=1; i<=N; ++i)
cnt += int(pie[i]/x);
if(cnt >= F+1)
return 1;
else
return 0;
}
int main()
{
//freopen("input.txt", "r", stdin);
cin >> T;
double rad;
double sum;
while(T--)
{
cin >> N >> F;
sum = 0.0;
for(int i=1; i<=N; ++i)
{
cin >> rad;
pie[i] = rad*rad*PI;
sum += pie[i];
}
double l = 0.0;
double r = sum/(F+1);
double mid;
while(r-l > 1e-6)
{
mid = (l+r)/2.0;
if(test(mid))
l = mid;
else
r = mid;
}
cout << fixed << setprecision(4) << mid << endl;
}
}