Blog·Tanky WooABOUTRSS

HDU/HDOJ 1969 Pie

01 Feb 2011
这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。

传送门:

http://acm.hdu.edu.cn/showproblem.php?pid=1969

分析:二分搜索

代码:

#include 
#include 
#include 
using namespace std;

double pie[10005];
int T, N, F;
double PI = acos(-1.0);

bool test(double x)
{
    int cnt = 0;
    for(int i=1; i<=N; ++i)
        cnt += int(pie[i]/x);
    if(cnt >= F+1)
        return 1;
    else
        return 0;
}

int main()
{
    //freopen("input.txt", "r", stdin);
    cin >> T;
    double rad;
    double sum;
    while(T--)
    {
        cin >> N >> F;
        sum = 0.0;
        for(int i=1; i<=N; ++i)
        {
            cin >> rad;
            pie[i] = rad*rad*PI;
            sum += pie[i];
        }
        double l = 0.0;
        double r = sum/(F+1);
        double mid;
        while(r-l > 1e-6)
        {
            mid = (l+r)/2.0;
            if(test(mid))
                l = mid;
            else
                r = mid;
        }
        cout << fixed << setprecision(4) << mid << endl;
    }
}