HDU4355 三分查找

/*
* 三分查找
*/
#include<cstdio>
#include<cmath>
#define eps 1e-6

//typedef __int64 LL;

int n;
double x[50005], w[50005];

double func(double y){
   double res=0;
   for(int i=0;i<n;i++){
       double a=y-x[i];
       a=a<0?-a:a;
       res+=a*a*a*w[i];
   }
   return res;
}

int main(){
   int T;
   scanf("%d",&T);
   for(int t=1;t<=T;t++){
       scanf("%d",&n);
       for(int i=0;i<n;i++){
           scanf("%lf%lf",&x[i],&w[i]);
       }
       double l=x[0],r=x[n-1],mid,mmid;
       while(r-l>eps){
           mid=(l+r)/2.0;
           mmid=(mid+r)/2.0;
           if(func(mid)-func(mmid)>eps){
               l=mid;
           }
           else{
               r=mmid;
           }
       }

printf("Case #%d: %lld\n",t,(long long)(func(r)+0.5));

//hdu要用int64

}
}

巴特西

HDU4355 三分查找

最新文章

热门文章