Cod sursa(job #2306672)

Utilizator usureluflorianUsurelu Florian-Robert usureluflorian Data 22 decembrie 2018 18:35:15
Problema Adapost 2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("adapost2.in");
ofstream g("adapost2.out");
const int nmax=5e4+3;
const int dx[4]={1,-1,0,0};
const int dy[4]={0,0,1,-1};
double x[nmax],y[nmax],cx,cy,a,b,sol;
int n,ok;
double usu(double a,double b)
{
    double sol=0;
    for(int i=1;i<=n;++i) sol+=sqrt((a-x[i])*(a-x[i])+(b-y[i])*(b-y[i]));
    return sol;
}
int main()
{
    f>>n;
    for(int i=1;i<=n;++i) f>>x[i]>>y[i];
    sol=usu(cx,cy);
    for(double d=500;d>=0.001;d/=2.0)
    {
        ok=0;
        for(int i=0;i<4;++i)
        {
            a=cx+1.0*dx[i]*d;
            b=cy+1.0*dy[i]*d;
            if(usu(a,b)<sol)
            {
                cx=a;
                cy=b;
                sol=usu(cx,cy);
                ok=1;
            }
        }
        if(ok) d*=2.0;
    }
    g<<setprecision(4)<<fixed<<cx<<' '<<cy;
    return 0;
}