学步园

//Telecasting station 2013.7.22
#include <iostream>
#include <cstdio>
using namespace std;
const int MAX = 15005;
const double EPS = 1e-6;
typedef struct xp{
    double x;
    double p;
}xp;

int n;
xp p[MAX];

double fabs(double x)
{
    if(x>0) return x;
    return (0-x);
}

double dspl(double m)
{
    double tmp = 0.0;
    for(int i=0;i<n;i++)
    {
        tmp += p[i].p*fabs(p[i].x-m);
        //cout<<"    tmp is "<<tmp;
    }

    return tmp;
}

int main()
{
    cin>>n;
    double l=0,r=0;
    for(int i=0;i<n;i++)
        cin>>p[i].x>>p[i].p;
    l = p[0].x;
    r = p[0].x;
    for(int i=1;i<n;i++)
    {
        if(p[i].x<l) l = p[i].x;
        if(p[i].x>r) r = p[i].x;
    }
    double lm,rm;
    while(l+EPS<r)
    {
        lm = l + (r-l)/3,rm = r - (r-l)/3;
        double lval = dspl(lm),rval = dspl(rm);
        //cout<<"lm = "<<lm<<"   lval = "<<lval<<"  rm = "<<rm<<"  rval = "<<rval<<endl;
        if(lval+EPS<rval) r = rm;
        else l = lm;
    }

    printf("%.5lf\n",lm);

    return 0;
}

三分和二分如出一辙。

函数的单极值性是前提，像这道题就是多个极值，好在任意输出就行。

用结构体也是很自然的事。

浮点数精度的问题。。若将EPS改成1e-5将得到PE。。。嗯。。总之是错的。***