HDU/HDOJ 1969 Pie

传送门:

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

分析:二分搜索

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <iostream>
#include <cmath>
#include <iomanip>
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;
    }
}

发布者

Tanky Woo

Tanky Woo,[个人主页:https://tankywoo.com] / [新博客:https://blog.tankywoo.com]

发表评论

电子邮件地址不会被公开。 必填项已用*标注