Cod sursa(job #1998793)

Utilizator refugiatBoni Daniel Stefan refugiat Data 9 iulie 2017 09:40:02
Problema Adapost 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#define ERR 0.0000000001
using namespace std;
ifstream si("adapost2.in");
FILE*so=fopen("adapost2.out","w");
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
int n;
struct pct
{
    double x,y;
};
pct v[1<<16];
inline double cost(pct p)
{
    double rez=0;
    for(int i=1;i<=n;++i)
        rez+=sqrt((p.x-v[i].x)*(p.x-v[i].x)+(p.y-v[i].y)*(p.y-v[i].y));
    return rez;
}
int main()
{
    si>>n;
    pct rez,nxt;
    for(int i=1;i<=n;++i)
    {
        si>>v[i].x>>v[i].y;
        rez.x+=v[i].x;
        rez.y+=v[i].y;
    }
    rez.x/=n;
    rez.y/=n;
    double sol=cost(rez),cur;
    for(double i=16;i>=0.0001;i/=2.0)
    {
        bool ok=false;
        for(int d=0;d<4;++d)
        {
            nxt={rez.x+i*dx[d],rez.y+i*dy[d]};
            cur=cost(nxt);
            if(sol-cur>=ERR)
            {
                sol=cur;
                rez=nxt;
                ok=true;
                break;
            }
        }
        if(ok)
        {
            i*=2;
        }
    }
    fprintf(so,"%.4f %.4f\n",rez.x,rez.y);
    return 0;
}