POJ 3122 Pie (二分＋精度)

Pie Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 11240 Accepted: 3919 Special Judge

Description

My birthday is coming up and traditionally I'm serving pie. Not just one pie, no, I have a number N of them, of various tastes and of various sizes. F of my friends are coming to my party and each of them gets a piece of pie. This should be one piece of one pie, not several small pieces since that looks messy. This piece can be one whole pie though.

My friends are very annoying and if one of them gets a bigger piece than the others, they start complaining. Therefore all of them should get equally sized (but not necessarily equally shaped) pieces, even if this leads to some pie getting spoiled (which is better than spoiling the party). Of course, I want a piece of pie for myself too, and that piece should also be of the same size.

What is the largest possible piece size all of us can get? All the pies are cylindrical in shape and they all have the same height 1, but the radii of the pies can be different.

Input

One line with a positive integer: the number of test cases. Then for each test case: One line with two integers N and F with 1 ≤ N, F ≤ 10 000: the number of pies and the number of friends.One line with N integers ri with 1 ≤ ri ≤ 10 000: the radii of the pies.

Output

For each test case, output one line with the largest possible volume V such that me and my friends can all get a pie piece of size V. The answer should be given as a floating point number with an absolute error of at most 10^?3.

Sample Input

3
3 3
4 3 3
1 24
5
10 5
1 4 2 3 4 5 6 5 4 2

Sample Output

25.1327
3.1416
50.2655

Source

Northwestern Europe 2006

題目鏈接：http://poj.org/problem?id=3122

題目大意：一個人有f個朋友，n個派，每個派都是圓柱形，高為1，半徑為ri，問怎樣均分可以使每人得到的盡量的大，這裡不可以拼接，比如一個派體積為6我要取其中的5，那剩余的1就沒用了，不能補到其他的4上面變成5，還有就是不光是分給朋友，自己也要的

題目分析：高恆定為1，因此分體積就是分面積，我們可以通過二分每人分到的面積來得到答案，這裡初始范圍的上限為所有的面積和除(f+1)注意這裡不是f，因為自己也要分到，下限是取半徑最小的那塊面積除(f+1)，因為不是整形，二分的時候設一個精度，因為答案是小數點後4位，我們就取1e-5，再二分前最好將半徑從大到小排序，這樣可以節省大量時間，二分的時候從大的依次往小的取，計算按當前的mid值最多可以分給多少人，注意若此時當前半徑下的派不夠分給一人時break，後面的就不用看了，因為我們已經按從大到小排序了，如果算出來的人數大於等於(f+1)說明分的面積小了，可以將mid擴大，否則說明分的面積大了，只能減小mid。

#include 
#include 
#include 
using namespace std;
int const MAX = 1e4;
double const PI = 4.0 * atan(1.0);
double const EPS = 1e-5;
double R[MAX];

bool cmp(double a, double b)
{
    return a > b;
}

int main()
{
    int T, n;
    scanf("%d", &T);
    while(T--)
    {
        double r, l, mid, sum = 0, mi = 1e10, f;
        scanf("%d %lf", &n, &f);
        f += 1;
        for(int i = 0; i < n; i++)
        {
            scanf("%lf", &R[i]);
            sum += (PI * R[i] * R[i]);
        }
        sort(R, R + n, cmp);
        r = sum / f;
        l = R[n - 1] * R[n - 1] * PI / f;
        mid = (l + r) / 2;
        while(r - l > EPS)
        {
            int cnt = 0;
            for(int i = 0; i < n; i++)
            {
                if((R[i] * R[i] * PI) / mid  > 1.0 - 1e-10)
                    cnt += (R[i] * R[i] * PI) / mid;
                else
                    break;
            }
            if(cnt >= f)
                l = mid + EPS;
            else
                r = mid - EPS;
            mid = (l + r) / 2;
        }
        printf("%.4f\n", mid);
    }
}