【杭电1969】Pie

心已赠人 2022-09-24 06:19 143阅读 0赞

![这里写图片描述][20160727093244009]  
![这里写图片描述][20160727093252280]

这题也是卡精度的二分题目，我只是一个π的定义方式不同就给wa，记得以后π的定义用const double PI = acos(-1.0),就是cos函数下求π，括号内要用浮点数。  
整体思路和我cable master那篇文章一样的。链接：  
[http://blog.csdn.net/better\_space/article/details/52039880][http_blog.csdn.net_better_space_article_details_52039880]

#include<stdio.h>
    #include<algorithm>
    #include<math.h>
    const double PI = acos(-1.0);//π的取值，先前直接PI=3.1415926死活不过,好桑心 
    double v[10005];
    int n,f;
    double area(double r) {
        return PI*r*r;
    }
    bool judge(double mid) {
        int cnt=0;
        for(int l=0; l<n; l++) {
            cnt+=(int)(v[l]/mid);
        }
        return cnt>=f+1;
    }
    int main() {
        int T;
        scanf("%d",&T);
        while(T--) {
            scanf("%d%d",&n,&f);
            double d,sum=0.0;
            for(int l=0; l<n; l++) {
                scanf("%lf",&d);
                v[l]=area(d);
                sum+=v[l];
            }
            double l=0.0,r=sum;
            double mid;
            while(fabs(l-r)>9*1e-7) {
                mid=(l+r)/2;
                if(judge(mid))
                    l=mid;
                else
                    r=mid;
            }
            printf("%.4lf\n",mid);
        }
        return 0;
    }

[http://acm.hdu.edu.cn/showproblem.php?pid=1969][http_acm.hdu.edu.cn_showproblem.php_pid_1969]

[20160727093244009]: /images/20220719/5fbf1dd54ba6455e8ea17a1239a06fca.png
[20160727093252280]: /images/20220719/8a5d77d5b41c4c2fa528124db7d68543.png
[http_blog.csdn.net_better_space_article_details_52039880]: http://blog.csdn.net/better_space/article/details/52039880
[http_acm.hdu.edu.cn_showproblem.php_pid_1969]: http://acm.hdu.edu.cn/showproblem.php?pid=1969