Cod sursa(job #1067161)

Utilizator auRSTARHreapca Aurelian auRSTAR Data 26 decembrie 2013 14:27:06
Problema Adapost 2 Scor 100
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2013 Marime 1.17 kb
#include<cstdio>
#include<vector>
#include<utility>
#include<cmath>
using namespace std;
vector<pair<double,double> >V;
pair<double,double> P;
double Dist,d,x,y,L,X,Y;
int i,n,DX[]={-1,0,0,1},DY[]={0,-1,1,0},ok,j;
double dist(double x1,double y1,double x2,double y2)
{
    return sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));
}
int main()
{
    freopen("adapost2.in","r",stdin);
    freopen("adapost2.out","w",stdout);
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        scanf("%lf%lf",&x,&y);
        V.push_back(make_pair(x,y));
        Dist+=dist(x,y,.0,.0);
    }
    P.first=.0f;P.second=.0f;
    for(L=1000.0;L>0.001f;L/=2)
    {
        ok=0;
        for(i=0;i<4;i++)
        {
            X=P.first+L*DX[i];Y=P.second+L*DY[i];
            d=0;
            for(vector<pair<double,double> >::iterator it=V.begin();it!=V.end();it++)
                d+=dist(it->first,it->second,X,Y);
            if(d<Dist)
            {
                ok=1;
                Dist=d;
                P.first=X;P.second=Y;
                break;
            }
        }
        if(ok)
            L*=2;
    }
    printf("%lf %lf",P.first,P.second);
    return 0;
}