HDU 4355 三分

题意：在一维数轴上给出点，每个点到求的那一点的距离为s，那么他的不高兴值就是s^3*w[i]，求导可以得出类似一个凹的图像，三分法求出的最小值。

#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
#define eps 1e-4
int n,t;
double x[50005],w[50005];
double getans(double s)
{
    double ans=0;
    for(int i=0; i<n; i++)
    {
        double s1=fabs(s-x[i]);
        ans+=s1*s1*s1*w[i];
    }
    return ans;
}
int main()
{
    int ca=0;
    scanf("%d",&t);
    while(t--)
    {
        double l,r;
        scanf("%d",&n);
        for(int i=0; i<n; i++)
            scanf("%lf%lf",&x[i],&w[i]);
        l=x[0],r=x[n-1];
        double mid1,mid2;
        while(r-l>1e-4)
        {
            mid1=l+(r-l)/3,mid2=r-(r-l)/3;
            if(getans(mid1)>getans(mid2))
                l=mid1+eps;
            else
                r=mid2-eps;
        }
        printf("Case #%d: %.0f\n",++ca,getans(l));
    }
    return 0;
}