Cod sursa(job #960593)

Utilizator primulDarie Sergiu primul Data 10 iunie 2013 19:47:47
Problema Adapost 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.45 kb
#include <cstdio>
#include <iostream>
#include <cmath>
 
using namespace std;
 
const double EPS = 1e-4;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
 
struct point
{
    double x, y;
};
 
int N;
point V[50010];
double X, Y;
 
inline double dist (const point &A, const point &B)
{
    return double (sqrt ((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y)));
}
 
inline double total_dist (const point &X)
{
    double ret = 0;
    int i;
 
    for (i = 1; i <= N; i ++)
        ret += dist (X, V[i]);
 
    return ret;
}
 
void Solve ()
{
    point P = {X, Y};
    double best = total_dist (P), now;
    double step = 512.0;
    bool ok;
    int i;
 
    while (step > EPS){
        ok = 0;
 
        for (i = 0; i < 4; i ++){
            point S = {P.x + step * dx[i], P.y + step * dy[i]};
            now = total_dist (S);
 
            if (now < best){
                best = now;
                P = S;
                ok = 1;
                break;
            }
        }
 
        if (!ok)
            step /= 2.0;
    }
    cout << P.x << " " << P.y;
}
 
int main()
{
    freopen ("adapost2.in", "r", stdin);
    freopen ("adapost2.out", "w", stdout);
 
    int i;
 
    scanf ("%d", &N);
 
    for (i = 1; i <= N; i ++){
        scanf ("%lf %lf", &V[i].x, &V[i].y);
        X += V[i].x;
        Y += V[i].y;
    }
    X /= N;
    Y /= N;
    Solve ();
 
    return 0;
}