Cod sursa(job #1669352)

Utilizator SmarandaMaria Pandele Smaranda Data 30 martie 2016 17:39:17
Problema Adapost 2 Scor 95
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.61 kb
#include <cstdio>
#include <cmath>

using namespace std;

const int N = 50002;
const double eps = 1.e-14;

struct Point {
    double x, y;
};

int n;
Point P [N];

double dist (const Point &A, const Point &B) {
    return sqrt ((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y));
}

double solve (const Point &G) {
    int i;
    double ans = 0;

    for (i = 1; i <= n; i ++)
        ans += dist (G, P [i]);
    return ans;
}

int main () {
    int i;
    double pas = 100, d1, d2, d3, d4, ans, d;
    Point G, Gn, G1, G2, G3, G4;

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

    scanf ("%d", &n);
    G.x = G.y = 0;
    for (i = 1; i <= n; i ++) {
        scanf ("%lf%lf", &P [i].x, & P [i].y);
        G.x += P [i].x;
        G.y += P [i].y;
    }
    G.x = G.x / n;
    G.y = G.y / n;
    d = solve (G);
    for (i = 1; i <= 40; i ++) {
        G1 = G2 = G3 = G4 = G;
        G1.x += pas;
        G2.y += pas;
        G3.x -= pas;
        G4.y -= pas;
        d1 = solve (G1);
        d2 = solve (G2);
        d3 = solve (G3);
        d4 = solve (G4);
        ans = d1; Gn = G1;
        if (d2 - ans <= -eps) {
            ans = d2;
            Gn = G2;
        }
        if (d3 - ans <= -eps) {
            ans = d3;
            Gn = G3;
        }
        if (d4 - ans <= -eps) {
            ans = d4;
            Gn = G4;
        }

        if (ans - d <= -eps) {
            G = Gn;
            d = ans;
        }
        else
            pas = pas / 2;
    }

    printf ("%f %f\n", G.x, G.y);
    return 0;
}