Cod sursa(job #130368)

Utilizator andrei_infoMirestean Andrei andrei_info Data 31 ianuarie 2008 22:16:57
Problema Adapost 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.43 kb
#include <cstdio>
#include <cstdlib>
#include <cmath>
#define MAX 50000

double px[MAX], py[MAX];

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

int N;
double xG, yG;

double dist(double pozx, double pozy)
{
    double rez = 0;
    for (int i = 0; i <N; i++)
    {
        double dx,dy;
        dx = px[i] - pozx;
        dy = py[i] - pozy;
        rez+= sqrt(dx*dx + dy*dy);
    };
    return rez;
}


void cauta_pc()
{
    double d = dist (xG, yG);
    double pas = 100;

    while ( pas > 0.0004 )
    {
        int gasit = 0;
        for (int i = 0; i<4; i++)
        {
            //4.1442 4.2898
            double new_x = xG + (double)pas*dx[i];
            double new_y = yG + (double)pas*dy[i];

            double aux = dist( new_x, new_y);

            if (aux < d )
            {
                d = aux;
                gasit = 1;
                xG = new_x;
                yG = new_y;
                break;

            };
        };
        if (!gasit)
            pas/=2;
    };
}

int main()
{
    freopen("adapost2.in", "r", stdin);
    freopen("adapost2.out", "w", stdout);

    scanf("%d\n", &N);
    for (int i =0;i<N;i++)
    {
        scanf("%lf %lf\n", &px[i], &py[i]);
        xG +=px[i]; yG+=py[i];
    };
    xG /= N;
    yG /= N;

    cauta_pc();

    printf("%lf %lf", xG, yG);

    fclose(stdin);
    fclose(stdout);
    return 0;
};