HDU1969 Pie(二分搜索)

HDU1969 Pie(二分搜索)

題目大意是要辦生日Party，有n個餡餅，有f個朋友，接下來是n個餡餅的半徑。然後是分餡餅了，
注意咯自己也要，大家都要一樣大，形狀沒什麼要求，但都要是一整塊的那種，也就是說不能從兩個餅中
各割一小塊來湊一塊，像面積為10的和6的兩塊餅（餅的厚度是1，所以面積和體積相等），
如果每人分到面積為5，則10分兩塊，6切成5，夠分3個人，如果每人6，則只能分兩個了！
題目要求我們分到的餅盡可能的大！

只要注意精度問題就可以了,一般WA 都是精度問題

運用2分搜索：

首先用總餅的體積除以總人數，得到每個人最大可以得到的V，但是每個人手中不能有兩片或多片拼成的一塊餅，

最多只能有一片分割過得餅。用2分搜索時，把0設為left，把V 設為right。mid=(left+right)/2;

搜索條件是：以mid為標志，如果每塊餅都可以分割出一個mid，那麼返回true,說明每個人可以得到的餅的體積可以

大於等於mid;如果不能分出這麼多的mid,那麼返回false,說明每個人可以得到餅的體積小於等於mid。

（1）精度為：0.000001

(2) pi 用反余弦求出，精度更高。

#include
#include
#include
using namespace std;
double pi = acos(-1.0);
int F,N;
double V[10001];
bool test(double x){
    int num=0;
    for(int i=0;i=F) return true;
    else return false;
}
int main()
{
    int t,r;
    double v,max,left,right,mid;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&N,&F);
        F = F + 1;
        for(int i=0;i 1e-6){
            mid = (left + right) / 2;
            if(test(mid)) left = mid;
            else right = mid;
        }
        printf("%.4lf\n",mid);
    }
    return 0;
}