Cod sursa(job #2067976)

Utilizator tifui.alexandruTifui Ioan Alexandru tifui.alexandru Data 16 noiembrie 2017 23:53:03
Problema Adapost 2 Scor 97
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <bits/stdc++.h>
#define coord_max 1000
#define Nmax 50001
#define eps 0.00001
#define x first
#define y second
using namespace std;
ifstream f("adapost2.in");
ofstream g("adapost2.out");
pair <double,double> pct[Nmax];
const double dx[4]={0,0,-1,1};
const double dy[4]={-1,1,0,0};
int n;
double sx,sy,best=(double)INT_MAX,D,nx,ny;
inline double dist()
{
    double ANS=0;
    for(int i=1;i<=n;i++)
        ANS+=sqrt((nx-pct[i].x)*(nx-pct[i].x)+(ny-pct[i].y)*(ny-pct[i].y));
    return ANS;
}
int main()
{
    f>>n;
    for(int i=1;i<=n;i++)
    {
        f>>pct[i].x>>pct[i].y;
        sx+=pct[i].x;
        sy+=pct[i].y;
    }
    sx/=n;
    sy/=n;
    for(double nr_iterations=3005;nr_iterations>=eps;nr_iterations*=0.56)
        for(int i=0;i<4;i++)
        {
            nx=sx+dx[i]*nr_iterations;
            ny=sy+dy[i]*nr_iterations;
            D=dist();
            if(D<best)
            {
                best=D;
                sx=nx;
                sy=ny;
            }
        }
    g<<fixed<<setprecision(4)<<sx<<' '<<sy;

    return 0;
}