UVa 12079 Pie

題意：
　　有N塊半徑Ri的pie要分給F+1(包含作者)個人，要把N塊pie平分成F+1片，每片大小需一樣，而且須完整，表示不能從兩塊pie切下來合併成一片，問一片最大的面積為多少。

想法：
　　使用binary search搜出答案。

	#include <cstdio>
	#include <cmath>
	using namespace std;
	int main()
	{
	const double pi = 2 * asin(1);
	int Case,N, F;
	int R[10001];
	scanf("%d",&Case);
	while (Case--){
	scanf("%d%d", &N, &F);
	F++;
	int UP = 0; // BS上界
	for (int i=0; i<N; i++){
	scanf("%d",&R[i]);
	R[i] *= R[i];
	if (R[i] > UP) UP = R[i];
	}
	double left = 0, right = UP;
	while (right-left > 0.00000001){
	double mid = (left+right)/2;
	int piece = 0;
	for (int i=0; i<N; i++)
	piece += R[i]/mid;
	if (piece >= F) left = mid; //片數大於人數 因此往上逼近
	else right = mid;
	}
	printf("%.3f\n",pi * left);
	}
	return 0;
	}

view raw [UVa] 12079 Pie.cpp hosted with ❤ by GitHub