Cod sursa(job #3348607)

Utilizator Radu_BicliBiclineru Radu Radu_Bicli Data 22 martie 2026 23:34:59
Problema Adapost 2 Scor 12
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <bits/stdc++.h>

using namespace std;

#define USE_STD_IO 0
#if USE_STD_IO
    #define fin cin
    #define fout cout
#else
    ifstream fin("adapost2.in");
    ofstream fout("adapost2.out");
#endif // USE_STD_IO

const int DX[] = {1, -1, 0, 0, 1, 1, -1, -1};
const int DY[] = {0, 0, 1, -1, 1, -1, 1, -1};
struct Punct {
    double x, y;
};
double px, py, lg;
Punct v[50002];
int n, i;

int main() {
    if(USE_STD_IO) ios_base::sync_with_stdio(false);
    fin.tie(NULL);
    fout.tie(NULL);

    fin >> n;
    for(i = 1; i <= n; i++) fin >> v[i].x >> v[i].y;

    lg = 500;
    px = py = 500;

    while(0.0001 < lg) {
        int dirmi = 0;
        double dmi = INT_MAX;
        for(int dir = 0; dir < 8; dir++) {
            int xn = px + lg * DX[dir];
            int yn = py + lg * DY[dir];

            double dist = 0;
            for(i = 1; i <= n; i++) {
                dist += sqrt((xn - v[i].x) * (xn - v[i].x) + (yn - v[i].y) * (yn - v[i].y));
            }
            if(dist < dmi) {
                dmi = dist;
                dirmi = dir;
            }
        }
        px += lg * DX[dirmi];
        py += lg * DY[dirmi];
        lg /= 2.0;
    }
    fout << setprecision(5) << fixed;
    fout << px << ' ' << py;

    return 0;
}