Cod sursa(job #1576162)

Utilizator retrogradLucian Bicsi retrograd Data 22 ianuarie 2016 10:08:09
Problema Adapost 2 Scor 67
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <iostream>
#include <algorithm>

using namespace std;

double X[50001], Y[50001];
int I[50001];

const int P = 3981721;

double dist(double x1, double y1, double x2, double y2) {
    x1 -= x2; y1 -= y2;
    return sqrt(x1*x1 + y1*y1);
}

int main() {
    freopen("adapost2.in", "r", stdin);
    freopen("adapost2.out", "w", stdout);

    int n;
    cin >> n;

    double x = 0, y = 0;

    for(int i=1; i<=n; i++) {
        cin >> X[i] >> Y[i];
        I[i] = i;
        x += X[i];
        y += Y[i];
    }

    x /= n;
    y /= n;

    for(int it=1; it * n <=1000000; it++) {
        random_shuffle(I+1, I+n+1);

        double dx = 0, dy = 0;

        for(int i=1; i<=n; i++) {
            double lambda = 0.1; //1.0 * (rand() % P + 1) / (P + 1);
            double distance = dist(X[I[i]], Y[I[i]], x, y);

            if(distance < 1e-12) continue;

            dx += lambda * (X[I[i]] - x) / distance;
            dy += lambda * (Y[I[i]] - y) / distance;
        }

        if(abs(dx) + abs(dy) <= 1e-5) break;

        x += dx;
        y += dy;

//        if(it % 100 == 0) {cerr << "Iteration " << it << ": " << x << " " << y << '\n';}
    }

    cout << x << " " << y;

    return 0;
}