hdu1969 Pie

/*************************************************************************
    > File Name: pie_hdu1969.cpp
    > Author: achiber
    > Mail: achiberx@gmail.com 
    > Created Time: 2014年03月07日 星期五 20时48分58秒
 ************************************************************************/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <cstring>
#include <stack>
#include <queue>
#include <cmath>

using namespace std;

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

double  A[maxn];
int n, f;

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

int main()
{
	int T;
	scanf("%d", &T);
	while(T--) 
	{
		scanf("%d%d", &n, &f);
		double maxa = -1;
		int r;
		for(int i = 0; i < n; i++){
			scanf("%d", &r);
			A[i] = PI*r*r;
			maxa = max(maxa, A[i]);
		}
		double L = 0.0, R = maxa;
		while(R-L > 1e-5)
		{
			double M = (L+R)/2;
			if(ok(M)) L = M;
			else R = M;
		}
		printf("%.4lf\n", L);
	}
	return 0;
}

hdu1969 Pie,布布扣,bubuko.com

hdu1969 Pie

原文：http://blog.csdn.net/achiberx/article/details/20938153