首页 > 代码库 > UVALive 3635 Pie(二分法)

UVALive 3635 Pie(二分法)

简单的二分法应用,循环1000次精度就满足要求了。

#include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>#include<string>#include<cmath>#include<map>#include<set>#include<vector>#include<algorithm>#include<stack>#include<queue>#include<cctype>#include<sstream>using namespace std;#define pii pair<int,int>#define LL long long intconst double eps=1e-10;const int INF=1000000000;const int maxn=10000+10;const double pi=acos(-1);int N,F,T;double r[maxn],maxr,s[maxn];bool ok(double x){    int f=0;    for(int i=0;i<N;i++)    {        f+=(int)(s[i]/x);        if(f>=F) return true;    }    return false;}int main(){    //freopen("in1.txt","r",stdin);    //freopen("out.txt","w",stdout);    scanf("%d",&T);    while(T--)    {        scanf("%d%d",&N,&F);        maxr=-1;        F++;        for(int i=0; i<N; i++)        {            scanf("%lf",&r[i]);            maxr=max(r[i],maxr);            s[i]=r[i]*r[i]*pi;        }        double L=0,R=maxr*maxr*pi;        for(int i=0;i<1000;i++)        {            double m=(L+R)/2;            if(ok(m)) L=m;            else R=m;        }        printf("%.4lf\n",R);    }    //fclose(stdin);    //fclose(stdout);    return 0;}

 

UVALive 3635 Pie(二分法)