uva - 12097 - Pie（二分法）

題意：有F+1個人來分N個圓形派，每個人得到的必須是一塊整派，而不是幾塊拼在一起的。要求得到的派面積要相同。求每個人最多得到多大面積的派。

方法：采用二分法，轉化為“是否可以讓每個人得到一塊面積為x的派”，取符合要求的最大x。（劉汝佳算訓P30）

#include <iostream>  
#include <iomanip>  
#include <string>  
#include <cstring>  
#include <cstdio>  
#include <queue>  
#include <stack>  
#include <algorithm>  
#include <cmath>  
#include <ctime>

using namespace std;

const double PI = acos(-1.0);
const int maxn = 10000+10;

int n, f;
double A[maxn];

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

int main() 
{
#ifdef Local    
	freopen("a.in", "r", stdin);    
#endif
	int t = 0, kase = 0;
	cin >> t;
	for (kase = 1; kase <= t; kase++)
	{
		int i = 0, j = 0;
		double _max = 0;
		cin >> n >> f;
		for (i = 0; i < n; i++)
		{
			int r = 0;
			cin >> r;
			A[i] = PI * r * r;
			_max = max(_max, A[i]);
		}
		double L = 0, R = _max;
		while(fabs(R-L) > 1e-5)
		{
			double M = (L+R)/2;
			if (judge(M))
				L = M;
			else
				R = M;
		}
		cout << fixed << setprecision(4) << L << endl;
	}
}
           

細節：注意循環條件，注意PI的表示方法。