Cod sursa(job #793465)

Utilizator repp4raduRadu-Andrei Szasz repp4radu Data 2 octombrie 2012 23:48:26
Problema Adapost 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <cstdio>
#include <cmath>

#define EPS 1e-4
#define MAX 65536

using namespace std;

struct punct
{
    double x, y;
}v[MAX], G, now;

double dist, act;
int n, dX[] = {-1, 0, 1, 0}, dY[] = {0, 1, 0, -1};

inline double getDistance(punct a)
{
    double rez = 0.0;
    for(int i = 1; i <= n; i++)
    {
        double distX = a.x - v[i].x, distY = a.y - v[i].y;
        rez += (sqrt(distX * distX + distY * distY));
    }
    return rez;
}

int main()
{
    freopen("adapost2.in", "r", stdin);
    scanf("%d\n", &n);
    for(int i = 1; i <= n; i++)
    {
        scanf("%lf %lf", &v[i].x, &v[i].y);
        G.x += v[i].x; G.y += v[i].y;
    } fclose(stdin);
    G.x /= n; G.y /= n; dist = getDistance(G);
    for(double adj = 512.0; adj > EPS; adj *= 0.5)
    {
        for(int i = 0; i < 4; i++)
        {
            now.x = G.x + dX[i] * adj; now.y = G.y + dY[i] * adj;
            act = getDistance(now);
            if(act < dist)
            {
                G.x = now.x; G.y = now.y;
                dist = act;
                adj *= 2;
                break;
            }
        }
    }
    freopen("adapost2.out", "w", stdout);
    printf("%.4lf %.4lf", G.x, G.y);
    fclose(stdout);
    return 0;
}