POJ 3122 Pie（ 二分搜索 ）

---

**链接：****传送门 **

题意：一个小朋友开生日派对邀请了 F 个朋友，排队上有 N 个 底面半径为 ri ，高度为 1 的派，这 F 个朋友非常不友好，非得“平分”这些派，每个人都不想拿到若干快小派，只想拿到一整块切好的派，当然形状可以不同，但是体积必须相同他们才能友好的玩下去......，现在求每个人能拿到的最大的派的体积是多少。

思路：

• 1.若N > F + 1 ，则从 N 个派中选出 F + 1 个比较大的，“平分”情况自然是这 F + 1 个最小的派
• 2.若N <= F + 1 ，就二分搜索一个能平分最大派的 S ，判断按照半径 S 分割这 N 个派能不能凑够 F + 1 个人的

---

/*************************************************************************

    > File Name: poj3122.cpp

    > Author:    WArobot

    > Blog:      http://www.cnblogs.com/WArobot/

    > Created Time: 2017年05月05日 星期五 16时28分37秒

 ************************************************************************/

#include<cstdio>

#include<cmath>

#include<cstdio>

#include<algorithm>

#include<iostream>

#include<iomanip>

using namespace std;

#define pi  3.1415926535898

#define eps 1e-5

#define dou double

#define maxn 10010

int N,F,t;

int ri[maxn];

dou S[maxn];

bool check(double s1){

	int cnt = 0;

	for(int i=0;i<N;i++){

		cnt +=	(int)(S[i]/s1);

	}

	if(cnt >= F+1)	return 1;

	else			return 0;

}

int main(){

	scanf("%d",&t);

	while(t--){

		scanf("%d%d",&N,&F);

		dou max_S = 0;

		for(int i=0;i<N;i++){

			scanf("%d",ri+i);

			S[i] = ri[i]*ri[i]*pi*1.0;

			max_S = max(max_S,S[i]);

		}

		if(N>F+1){

			sort(ri,ri+N);

			dou ans = ri[N-(F+1)]*ri[N-(F+1)]*1.0*pi;

			cout<<fixed<<setprecision(4)<< ans <<endl;

		}else{

			// 二分找最大面积

			dou l = 0.0 , r = max_S+10 , mid;

			while(r-l>eps){

				mid = (l+r)/2;

				if(check(mid))	l = mid;

				else			r = mid;

			}

			dou ans = (l+r)/2;

			cout<<fixed<<setprecision(4)<< ans <<endl;

		}

	}

	return 0;

}