Cod sursa(job #810442)

Utilizator visanrVisan Radu visanr Data 10 noiembrie 2012 12:42:01
Problema Adapost 2 Scor 95
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <vector>
using namespace std;


const int dx[4] = {-1, 0, 0, 1};
const int dy[4] = {0, -1, 1, 0};

#define mp make_pair
#define pd pair<double, double>
#define x first
#define y second
#define eps 0.0001

pd ans, now, V[50010];
int N;

double Dist(pd A)
{
    double crt = 0.0;
    for(int i = 1; i <= N; i++)
        crt += sqrt((A.x - V[i].x) * (A.x - V[i].x) + (A.y - V[i].y) * (A.y - V[i].y));
    return crt;
}

int main()
{
    freopen("adapost2.in", "r", stdin);
    freopen("adapost2.out", "w", stdout);
    scanf("%i", &N);
    for(int i = 1; i <= N; i++)
    {
        scanf("%lf %lf", &V[i].x, &V[i].y);
        ans.x += V[i].x;
        ans.y += V[i].y;
    }
    ans.x /= N;
    ans.y /= N;
    double crt = Dist(ans);
    for(double step = 500; step > eps; step /= 2)
        for(int i = 0; i < 4; i++)
        {
            now.x = ans.x + step * dx[i];
            now.y = ans.y + step * dy[i];
            if(Dist(now) < crt)
            {
                crt = Dist(now);
                ans = now;
                step *= 2;
                break;
            }
        }
    printf("%.4lf %.4lf\n", ans.x, ans.y);
    return 0;
}