Cod sursa(job #2987812)

Utilizator rares89_Dumitriu Rares rares89_ Data 2 martie 2023 21:45:58
Problema Adapost 2 Scor 94
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <fstream>
#include <cmath>
#include <iomanip>
#define INF 0x3f3f3f3f

using namespace std;

ifstream fin("adapost2.in");
ofstream fout("adapost2.out");

const int di[] = {-1, 0, 1, 0};
const int dj[] = {0, 1, 0, -1};

int n;
double a[50005], b[50005], x, y, d, v;

double dist(double x, double y) {
    // daca se iese din lim date
    if(x < 0.0 || x > 1000.0 || y < 0.0 || y > 1000.0) {
        return INF;
    }
    double ans = 0;
    for(int i = 1; i <= n; i++) {
        ans += sqrt((x - a[i]) * (x - a[i]) + (y - b[i]) * (y - b[i]));
    }
    return ans;
}

void solve() {
    for(int dd = 0; dd < 4; dd++) {
        double val = dist(x + v * di[dd], y + v * dj[dd]);
        if(d > val) {
            d = val;
            x = x + v * di[dd];
            y = y + v * dj[dd];
        }
    }
    v /= 2;
    if(v < 0.0001) {
        return;
    }
    solve();
}

int main() {
    fin >> n;
    for(int i = 1; i <= n; i++) {
        fin >> a[i] >> b[i];
    }
    v = 250.0;
    x = y = 500.0; // plec de la jumate
    d = dist(x, y);
    solve();
    fout << fixed << setprecision(5) << x << " " << y;
    return 0;
}