Cod sursa(job #1385341)

Utilizator george_stelianChichirim George george_stelian Data 11 martie 2015 21:31:05
Problema Adapost 2 Scor 35
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <cstdio>
#include <cmath>

using namespace std;

const double eps=0.000001;
const int auxx[4]={-1,0,1,0},auxy[4]={0,1,0,-1};
struct punct
{
    double x,y;
}v[50010];
int n;

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

int main()
{
    freopen("adapost2.in", "r", stdin);
    freopen("adapost2.out", "w", stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%lf%lf",&v[i].x,&v[i].y);
    double x=500,y=500,s=dist(500,500),pas=500;
    while(pas>eps)
    {
        int k=0;
        for(int i=0;i<4;i++)
        {
            double s1=dist(x+auxx[i]*pas,y+auxy[i]*pas);
            if(s1<s)
            {
                s=s1;
                x+=auxx[i]*pas;
                y+=auxy[i]*pas;
                k=1;
                break;
            }
        }
        if(!k) pas/=2.0;
    }
    printf("%lf %lf",x,y);
    return 0;
}