Cod sursa(job #3348618)

Utilizator Radu_BicliBiclineru Radu Radu_Bicli Data 22 martie 2026 23:49:58
Problema Adapost 2 Scor 97
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.46 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 double DX[] = {1, -1, 0, 0, 1, 1, -1, -1};
const double DY[] = {0, 0, 1, -1, 1, -1, 1, -1};
struct Punct {
    double x, y;
};
double px, py, lg;
Punct v[50002];
int n, i;

static inline double Dist(double px, double py) {
    if(!(0.0 <= px && px <= 1000.0 && 0.0 <= py && py <= 1000.0)) {
        return INT_MAX - 102;
    }
    double dist = 0;
    for(i = 1; i <= n; i++) {
        dist += sqrt((px - v[i].x) * (px - v[i].x) + (py - v[i].y) * (py - v[i].y));
    }
    return dist;
}

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 = 250;
    px = py = 500;

    double dmi = Dist(px, py);
    while(true) {
        for(int dir = 0; dir < 4; dir++) {
            double xn = px + lg * DX[dir];
            double yn = py + lg * DY[dir];

            double dist = Dist(xn, yn);
            if(dist < dmi) {
                dmi = dist;
                px += lg * DX[dir];
                py += lg * DY[dir];
            }
        }
        lg /= 2.0;
	if(lg < 0.0001) break;
    }
    fout << setprecision(5) << fixed;
    fout << px << ' ' << py;

    return 0;
}