Cod sursa(job #2315514)

Utilizator BlackLordFMI Alex Oprea BlackLord Data 10 ianuarie 2019 03:34:59
Problema Adapost 2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <fstream>
#include <iomanip>
#include <cmath>

using namespace std;

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

const int INF = (1 << 30) - 1;
const int N = 50010;

int n, i;
double x, y, a[N], b[N], v, d, rez;

int da[4] = {1, 0, -1, 0};
int db[4] = {0, 1, 0, -1};

double dist(double x, double y) {
    if (x < 0.0 || x > 1000.0 || y < 0.0 || y > 1000.0) {
        return INF;
    }
    rez = 0;
    for (i = 1; i <= n; ++i) {
        rez = rez + sqrt((x - a[i]) * (x - a[i]) + (y - b[i]) * (y - b[i]));
    }
    return rez;
}

void adapost() {
    double aux;
    for (int D = 0; D < 4; ++D) {
        aux = dist(x + v * da[D], y + v * db[D]);
        if (aux < d) {
            x = x + v * da[D];
            y = y + v * db[D];
            d = aux;
        }
    }
    v /= 2;
    if (v < 0.0001) {
        return;
    }
    adapost();
}

int main() {
    fin >> n;
    for (i = 1; i <= n; ++i) {
        fin >> a[i] >> b[i];
    }
    v = 250;
    x = 500;
    y = 500;
    d = dist(x, y);
    adapost();
    fout << setprecision(5);
    fout << fixed << x << " " << y << "\n";
    return 0;
}