Cod sursa(job #2276440)

Utilizator iulianrotaruRotaru Gheorghe-Iulian iulianrotaru Data 4 noiembrie 2018 18:51:06
Problema Adapost 2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.02 kb
#include<bits/stdc++.h>
using namespace std;
ifstream f("adapost2.in");
ofstream g("adapost2.out");
const double EPS=0.0000000001;
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
int n,i,d;
struct pt
{
    double x,y;
}rez,nxt,V[1<<16];
double cost(pt X)
{
    double rez=0;
    for(int i=1;i<=n;++i)
        rez+=sqrt((X.x-V[i].x)*(X.x-V[i].x)+(X.y-V[i].y)*(X.y-V[i].y));
    return rez;
}
int main()
{
    f>>n;
    for(i=1;i<=n;++i)
    {
        f>>V[i].x>>V[i].y;
        rez.x+=V[i].x;
        rez.y+=V[i].y;
    }
    rez.x/=n;
    rez.y/=n;
    double bst=cost(rez),act;
    for(double step=16;step>=0.0001;step/=2.0)
    {
        bool ok=0;
        for(d=0;d<4;++d)
        {
            nxt={rez.x+step*dx[d],rez.y+step*dy[d]};
            act=cost(nxt);
            if(bst-act>=EPS)
            {
                bst=act;
                rez=nxt;
                ok=1;
                break;
            }
        }
        if(ok) step*=2.0;
    }
    g<<rez.x<<' '<<rez.y;
    return 0;
}