Cod sursa(job #1046661)

Utilizator mariacMaria Constantin mariac Data 3 decembrie 2013 12:02:48
Problema Adapost 2 Scor 95
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.52 kb
#include <fstream>
#include <math.h>

using namespace std;
ifstream fin("adapost2.in");
FILE *f = fopen("adapost2.out", "w");

int N;
double x[50005], y[50005];
double dmin = 200000000;
double dist(int i, int j)
{
    double xx = x[i]-x[j], yy = y[i] - y[j];
    return sqrt( xx * xx + yy * yy);
}
double suma_dist(double a, double b)
{
    double s = 0;
    x[N + 1] = a; y[N + 1] = b;
    for( int i = 1; i <= N; i++)
        s += dist(i, N+1);
    return s;
}
int main()
{
    int i;
    double sx = 0, sy = 0,abat = 250;

    fin>>N;

    for( i = 1; i <= N; i++)
    {
        fin>>x[i]>>y[i];
        sx += x[i];
        sy += y[i];
    }
    sx /= N;
    sy /= N;
    while(abat > 0.0005)
    {
        double f;
        f = suma_dist(sx + abat, sy);
        if( f  < dmin)
            {
                dmin = f;
                sx += abat;
                continue;
            }
        f = suma_dist(sx - abat, sy);
        if( f  < dmin)
            {
                dmin = f;
                sx -= abat;
                continue;
            }
        f = suma_dist( sx, sy + abat);
        if( f  < dmin)
            {
                dmin = f;
                sy += abat;
                continue;
            }
        f = suma_dist( sx, sy - abat);
        if( f  < dmin)
            {
                dmin = f;
                sy -= abat;
                continue;
            }
        abat = abat / 2;
    }

    fprintf(f,"%.4f %.4f",sx, sy);

    return 0;
}