Cod sursa(job #1972846)

Utilizator georgerapeanuRapeanu George georgerapeanu Data 23 aprilie 2017 20:31:43
Problema Adapost 2 Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <cstdio>
#include <algorithm>
#define x first
#define y second
using namespace std;
FILE *f=fopen("adapost2.in","r");
FILE *g=fopen("adapost2.out","w");
int N;
pair<long double,long double> V[50005];
long double di=100000000;
long double dist(pair<long double,long double> a,pair<long double,long double> b)
{
    return sqrt(pow(a.x-b.x,2)+pow(a.y-b.y,2));
}
long double check(pair<long double,long double> a)
{
    long double rez=0;
    for(int i=1;i<=N;i++)
        rez+=dist(a,V[i]);
    return rez;
}
pair<long double,long double> a,b;
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};
int main()
{
    fscanf(f,"%d",&N);
    for(int i=1;i<=N;i++)
        {fscanf(f,"%Lf %Lf",&V[i].x,&V[i].y);a.x+=V[i].x;a.y+=V[i].y;}
    a.x/=(long double)N;
    b.x/=(long double)N;
    long double D=1000;
    while(D>=0.001)
    {
        bool ok=0;
        long double minim=100000000;
        for(int k=0;k<4;k++)
        {
            if(minim>check({a.x+D*dx[k],a.y+D*dy[k]}))
                {b={a.x+D*dx[k],a.y+D*dy[k]};minim=check(b);}
        }
        if(minim<di){di=minim;a=b;ok=1;}
        if(ok==0)D/=2;
    }
    fprintf(g,"%.10Lf %.10Lf",a);
    fclose(f);
    fclose(g);
    return 0;
}