HDU 4355

三分法

[cpp] 
#include<cstdio> 
#include<string> 
#include<cmath> 
#include<algorithm> 
using namespace std; 
#define N 50010 
double p[N],w[N]; 
int n; 
double cal(double mid){ 
    int i; 
    double ans=0; 
    for(i=1;i<=n;i++){ 
        double err=fabs(mid-p[i]); 
        ans+=w[i]*err*err*err; 
    } 
    return ans; 
} 
int main(){ 
    int t,T; 
    int i; 
    scanf("%d",&T); 
    for(t=1;t<=T;t++){ 
        scanf("%d",&n); 
        for(i=1;i<=n;i++) 
            scanf("%lf %lf",&p[i],&w[i]); 
        double l=-1000000,r=1000000; 
        while(r-l>1e-4){ 
            double ll=(l*2+r)/3; 
            double rr=(l+r*2)/3; 
            double ans1=cal(ll); 
            double ans2=cal(rr); 
            if(ans1>ans2) 
                l=ll; 
            else 
                r=rr; 
        } 
        printf("Case #%d: %.0lf\n",t,cal(l)); 
    } 
}