poj 3122 Pie

【题目链接】

题目意思

T组数据，每组数据给你两个正整数N(N<10000)，M(M<10000)，N表示下面有N个派，M表示有M个朋友(所以要m++，QAQ)，其中每个人拿到的派必须是一整块，并且大小必须一样，求每个人拿到的派的最大值。
误差允许在1e-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

思路分析

首先想到二分答案，其次由于每个人的派的形状并不固定，所以二分面积以减小误差，枚举范围 0-最大面积*2。

#include <iostream>
#include <algorithm>
#include <cmath>
#define PI (acos(-1.0))
using namespace std;
int a[10005], n, m;
int judge(double k)
{
    int count = 0;
    for (int i = 1; i <= n; i++)
        count += a[i] * a[i] / k;
    if (count >= m)
        return true;
    else
        return false;
}
int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        int mx = 0;
        scanf("%d%d", &n, &m);
        m++;
        for (int i = 1; i <= n; i++)
        {
            scanf("%d", &a[i]);
            mx = max(mx, a[i]);
        }
        double head = 0, tail = mx * mx * 2;
        while (head + 0.000001 < tail)
        {
            double mid = (head + tail) / 2;
            if (judge(mid))
                head = mid;
            else
                tail = mid;
        }
        printf("%.4lf\n", PI*head);
    }
}