Cod sursa(job #929164)

Utilizator alexalghisiAlghisi Alessandro Paolo alexalghisi Data 26 martie 2013 21:29:29
Problema Adapost 2 Scor 12
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.27 kb
#include <iostream>
#include <fstream>
#include <cmath>
#include <iomanip>
#define per pair<double,double>
#define mp make_pair
#define DN 50005
#define EPS 1e-6
#define x first
#define y second
using namespace std;

int n;
per p[DN],pct;
double d=500.0,sum=1<<30;

ifstream f("adapost2.in");
ofstream g("adapost2.out");

double dist(per a,per b)
{
    return sqrt( (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y) );
}

double get_sum ( per x )
{
    double S=0;
    for(int i=1;i<=n;++i)
        S+=dist(x,p[i]);
    return S;
}

void caut()
{
    while(d>EPS)
    {
        double s1= get_sum(mp(pct.x+d,pct.y)) , s2= get_sum(mp(pct.x-d,pct.y)), s3= get_sum(mp(pct.x,pct.y+d)) , s4= get_sum(mp(pct.x,pct.y-d));
        double mini=min(s1,min(s2,min(s3,s4)));
        if(mini<sum)
        {
            sum=mini;
            if(s1==mini)
                pct.x+=d;
            if(s2==mini)
                pct.x-=d;
            if(s3==mini)
                pct.y+=d;
            if(s4==mini)
                pct.y-=d;
        }
        else
           d/=2.0;

    }
    g<<fixed<<setprecision(4)<<pct.x<<" "<<pct.y;
}

int main()
{
    f>>n;
    for(int i=1;i<=n;++i)
    {
       f>>p[i].x>>p[i].y;
       pct.x+=p[i].x;
       pct.y+=p[i].y;
    }
    pct.x/=n;
    pct.y/=n;
    caut();

    return 0;
}