三分 例题

K - 例题4

Time Limit:1000MS     Memory Limit:65536KB     64bit IO Format:%I64d & %I64u

Submit Status Practice POJ 2420

Description

给出平面上N（<=100）个点，你需要找到一个这样的点，使得这个点到N个点的距离之和尽可能小。输出这个最小的距离和（四舍五入到最近的整数）。

Input

第一行N，接下来N行每行两个整数，表示N个点

Output

一行一个正整数，最小的距离和。

Sample Input

4
0 0
0 10000
10000 10000
10000 0

Sample Output

28284

#include <stdio.h> 
#include <math.h>
const double inf=1e9+7;

int n;
double a[105],b[105];

double Cal(double x,double y)
{
    int i;    double s=0;
    for(i=1;i<=n;i++)
    {
        s=s+sqrt((x-a[i])*(x-a[i])+(y-b[i])*(y-b[i]));
    }
    return s;
}

double C(double x)
{
    int i;    double l=-inf,u=inf,m,mm;
    for(i=1;i<=100;i++)
    {
        m=(l+u)/2.0;
        mm=(m+u)/2.0;
        if(Cal(x,m)<=Cal(x,mm))
        {
            u=mm;
        }
        else
        {
            l=m;
        }
    }
    return Cal(x,u);
}

int main()
{
    int i,j;
    while(scanf("%d",&n)!=EOF)
    {
        for(i=1;i<=n;i++)
            scanf("%lf %lf",&a[i],&b[i]);
        double xlb=-inf,xub=inf;
        for(i=1;i<=100;i++)
        {
            double xmid=(xlb+xub)/2.0,mxmid=(xmid+xub)/2.0;
            if(C(xmid)<=C(mxmid))
            {
                xub=mxmid;
            }
            else
            {
                xlb=xmid;
            }
        }
        printf("%.lf
",C(xub));
    }
    return 0;
}