Cod sursa(job #1106828)

Utilizator paunmatei7FMI Paun Matei paunmatei7 Data 13 februarie 2014 11:18:05
Problema Adapost 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.36 kb
#include <cstdio>
#include <algorithm>
#include <cmath>

#define x first
#define y second
#define NMAX 50007
#define EPS 0.00001

using namespace std;

const int dx[] = {0, 1, -1, 0,  0};
const int dy[] = {0, 0,  0, 1, -1};
int n;
pair< double, double > Ans, a[NMAX];

double solve(double X, double Y){
    double Sum = 0.0;
    for(int i = 1; i <= n; ++i)
        Sum += (double) sqrt( (double) (X - a[i].x) * (X - a[i].x) + (Y - a[i].y) * (Y - a[i].y));
    return Sum;
}

int main(){
    freopen("adapost2.in", "r", stdin);
    freopen("adapost2.out", "w", stdout);
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i){
        scanf("%lf %lf", &a[i].x, &a[i].y);
        Ans.x += a[i].x;
        Ans.y += a[i].y;
    }
    Ans.x /= n;
    Ans.y /= n;
    double Cost = solve(Ans.x, Ans.y);
    for(double i = 16.0; i >= 0.001; i = i / 2.0){
        int ok = 0;
        for(int j = 1; j <= 4; ++j){
            pair< double, double > Act;
            Act.x = Ans.x + i * dx[j];
            Act.y = Ans.y + i * dy[j];
            double NewCost = solve(Act.x, Act.y);
            if(Cost - NewCost >= EPS){
                Cost = NewCost;
                Ans = Act;
                ok = 1;
                break;
            }
        }
        if(ok == 1)
            i *= 2.0;
    }
    printf("%lf %lf", Ans.x, Ans.y);
    return 0;
}