Cod sursa(job #329445)

Utilizator ssergiussSergiu-Ioan Ungur ssergiuss Data 6 iulie 2009 11:48:48
Problema Adapost 2 Scor 70
Compilator cpp Status done
Runda splunge1 Marime 1.62 kb
# include <algorithm>
# include <math.h>
using namespace std;

# define DIM 50001

struct pct {

    double x, y;
};

int n;
double min0, ax[ DIM ], ay[ DIM ];

inline double min ( double x, double y, double z, double w ) {

    if ( x < y && x < z && x < w )
	return x;

    if ( y < x && y < z && y < w )
	return y;

    if ( z < x && z < y && z < w )
	return z;

    return w;
}

double calc ( double x, double y ) {

    int i;
    double d;

    d = 0;
    for ( i = 1; i <= n; ++ i )
	d += sqrt ( ( x - ax[ i ] ) * ( x - ax[ i ] ) + ( y - ay[ i ] ) * ( y - ay[ i ] ) );

    return d;
}

void solve () {

    int i;
    double p, d0, d1, d2, d3;
    pct aux;

    scanf ( "%d", &n );
    for ( i = 1; i <= n; ++ i )
	scanf ( "%lf%lf", &ax[ i ], &ay[ i ] );
    aux.x = 1234;
    aux.y = 4321;
    min0 = 50000001;
    for ( p = 1000; p > 0.0001; ) {

	d0 = calc ( aux.x - p, aux.y );
	d1 = calc ( aux.x + p, aux.y );
	d2 = calc ( aux.x, aux.y - p );
	d3 = calc ( aux.x, aux.y + p );
	if ( d0 > min0 && d1 > min0 && d2 > min0 && d3 > min0 )
	    p = p / 2;
	else if ( min ( d0, d1, d2, d3 ) == d0 ) {

	    aux.x -= p;
	    min0 = d0;
	}
	else if ( min ( d0, d1, d2, d3 ) == d1 ) {

	    aux.x += p;
	    min0 = d1;
	}
	else if ( min ( d0, d1, d2, d3 ) == d2 ) {

	    aux.y -= p;
	    min0 = d2;
	}
	else if ( min ( d0, d1, d2, d3 ) == d3 ) {

	    aux.y += p;
	    min0 = d3;
	}
    }
    printf ( "%lf %lf", aux.x, aux.y );
}

int main () {

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

    solve ();

    return 0;
}