poj 3122 (二分查找)

poj 3122 (二分查找)

鏈接:poj 3122

題意：我生日派對時，准備了n個圓柱形的pie,半徑比一定相同，但高都為1，

邀請了f個朋友，加上自己一共f+1人，需要將n個pie分給f+1個人

要求：每個人分得的pie尺寸要一樣大，

並且同一個人所分的pie要是從同一個pie上得到的，n個pie分完後可以有剩余

求：每個人最多可以分多少

分析：因為同一個人所分的pie都來自同一個pie，

若每個人所分的最大體積為a,那麼比a小的pie肯定得捨棄。

將每個人最多分得的pie看成半徑為r的圓柱，則最大尺寸為PI*r*r*1,

可以用二分算法，下界為0，上界為pie的最大半徑

要注意精度問題

#include
#include
#define PI acos(-1.0)
#define eps 1e-8
int n,m;
double rad[10010];
bool judge(double size)
{
    int cnt=0;
    for(int i=1;i<=n;i++)
        cnt+=(int)(rad[i]*rad[i]/(size*size));
    if(cnt>=m)
        return true;
    return false;
}
double bin_search(double l,double r)
{
    double mid;
    while(r-l>eps){
        mid=(l+r)/2;
        if(judge(mid))  //判斷分該半徑的pie是否夠分
            l=mid;
        else
            r=mid;
    }
    return mid;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        m++;
        double r=0;
        for(int i=1;i<=n;i++){
            scanf("%lf",&rad[i]);
            if(rad[i]>r)
                r=rad[i];
        }
        double ansR=bin_search(0.0,r);
        printf("%.4lf\n",PI*ansR*ansR);
    }
    return 0;
}