Cod sursa(job #1064307)

Utilizator mirceadinoMircea Popoveniuc mirceadino Data 21 decembrie 2013 18:51:38
Problema Adapost 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
#include<cstdio>
#include<utility>
#include<cmath>

using namespace std;

typedef pair<double,double> Point;
const int NMAX = 50005;

int N;
Point P[NMAX],O,Q;
double SDist,L,sdist;
int Dx[]={0,0,-1,1};
int Dy[]={-1,1,0,0};

inline double dist(Point A,Point B)
{
    return sqrt((A.first-B.first)*(A.first-B.first) + (A.second-B.second)*(A.second-B.second));
}

int main()
{
    int i,j,ok;
    freopen("adapost2.in","r",stdin);
    freopen("adapost2.out","w",stdout);
    scanf("%d",&N);
    O=make_pair(0.0,0.0);
    L=1000.0;
    for(i=1;i<=N;i++)
    {
        scanf("%lf%lf",&P[i].first,&P[i].second);
        SDist+=dist(P[i],O);
    }
    while(L>0.001)
    {
        ok=0;
        for(i=0;i<4;i++)
        {
            sdist=0;
            Q=make_pair(O.first+Dx[i]*L,O.second+Dy[i]*L);
            for(j=1;j<=N;j++)
                sdist+=dist(P[j],Q);
            if(sdist<SDist)
            {
                SDist=sdist;
                O=Q;
                ok=1;
                break;
            }
        }
        if(ok) continue;
        L/=2.0;
    }
    printf("%.4lf %.4lf\n",O.first,O.second);
    return 0;
}