Cod sursa(job #929254)

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

int n;
per p[DN],pct;
double d=512.0,sum=1<<30;
int ii[]={1,-1,0,0},jj[]={0,0,-1,1};

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

double get_sum ( per a )
{
    double S=0;
    for(int i=1;i<=n;++i)
    {
        double dx=(a.x-p[i].x) , dy=(a.y-p[i].y);
        S+=sqrt(dx*dx+dy*dy);
    }
    return S;
}

void caut()
{
    for(double d=16.0;d>=EPS;d*=0.5)
    {
        for(int t=0;t<4;++t)
        {
            per new_point = mp(pct.x + ii[t]*d , pct.y + jj[t] *d );
            double new_sum = get_sum( new_point );

            if(new_sum<sum)
            {
                sum=new_sum;
                pct=new_point;
                d*=2;
                break;
            }
        }
    }
    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;
    get_sum(pct);
    caut();

    return 0;
}