【二分法】poj 3122 分批萨

poj 3122 分批萨"/>

【二分法】poj 3122 分批萨

题目来源：poj 3122
参考：

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
int n, f;
const int maxn = 10010;
const double pi = acos(-1.0);
int a[maxn];
const double eps = 0.0001;bool judge(double weight)
{int cnt = 0;for (int i = 0; i < n; i++){cnt += (int)(a[i] / weight);}if (cnt < f){return false;}else{return true;}
}int main()
{int T;cin >> T;while (T--){cin >> n >> f;double low = 0;double high = 0;int temp = 0;for (int i = 0; i < n; i++){cin >> a[i];a[i] *= a[i];temp = max(a[i], temp);}high = temp;double mid = 0;sort(a, a + n);f++;while (high - low > eps){mid = (low + high) / 2;if (judge(mid)){low = mid;}else{high = mid;}}printf("%.4f\n", pi * mid);}return 0;
}