Cod sursa(job #1075458)

Utilizator mathboyDragos-Alin Rotaru mathboy Data 8 ianuarie 2014 23:42:36
Problema Adapost 2 Scor 90
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2013 Marime 1.28 kb
#include <cstdio>
#include <cmath>
 
#define MAXN 50005
using namespace std;
 
struct Point {
    double x, y;
} p[MAXN];
 
long double Sdist = 100000000;
const double eps = 0.000001;
int N;
int dx[] = {0, -1, 0, 1};
int dy[] = {1, 0, -1, 0};
inline double calc(double x1, double y1, double x2, double y2) {
    return sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1));
}
inline bool isGood(long double gX, long double gY)
{   
    long double dist = 0;
    for(int i = 1; i <= N; i++) 
        dist += calc(p[i].x, p[i].y, gX, gY);
    if (dist < Sdist) {
        Sdist = dist;
        return 1;
    }
    return 0;
}
int main () {
 
    freopen("adapost2.in", "r", stdin);
    freopen("adapost2.out", "w", stdout);
 
    scanf("%d\n", &N);
     
    int i, k;
    long double gx = 0, gy = 0;
 
    for(i = 1; i <= N; i++) {
        scanf("%lf %lf\n", &p[i].x, &p[i].y);
        gx += p[i].x;
        gy += p[i].y;
    }
    gx /= N;
    gy /= N;
     
    isGood(gx, gy);
    for(double lim = 1025; lim > eps; ) {
        for(k = 0; k < 4; k++)
            if(isGood(gx + lim * dx[k], gy + lim * dy[k])) {
                gx += lim * dx[k];
                gy += lim * dy[k];
                break;
            }
        if (k == 4) lim /= 2.0;
    }
    printf("%.4Lf %.4Lf\n", gx, gy);
    return 0;
}