Cod sursa(job #2711729)

Utilizator bem.andreiIceman bem.andrei Data 24 februarie 2021 17:09:47
Problema Adapost 2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <bits/stdc++.h>

using namespace std;
ifstream r("adapost2.in");
ofstream w("adapost2.out");
int n, nr=38, dx[]= {0, 1, 0, -1}, dy[]= {1, 0, -1, 0};
double px, py, dmin=1000000000, t, pas=512, x[50003], y[50003];
int main()
{
    r>>n;
    for(int i=1;i<=n;i++)
    {
        r>>x[i]>>y[i];
        px+=x[i];
        py+=y[i];
    }
    px/=n;
    py/=n;
    if(n<10000){
        nr=50;
    }
    for(int i=1;i<=nr;i++){
        pas/=2;
        for(int j=0;j<4;j++)
        {
            t=0;
            for(int i=1; i<=n; i++){
                t+=sqrt((px+pas*dx[j]-x[i])*(px+pas*dx[j]-x[i])+(py+pas*dy[j]-y[i])*(py+pas*dy[j]-y[i]));
            }
            if(t<dmin)
            {
                dmin=t;
                px+=pas*dx[j];
                py+=pas*dy[j];
                pas*=2;
                break;
            }
        }
    }
    w<<px<<" "<<py<<"\n";
    return 0;
}