Cod sursa(job #594464)

Utilizator mathboyDragos-Alin Rotaru mathboy Data 7 iunie 2011 19:17:19
Problema Adapost 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <cstdio>
#include <cmath>

#define MAXN 50005
using namespace std;

struct Point {
	double x, y;
} p[MAXN];

long double Sdist = 100000000;
const double eps = 0.000001;
int N;
int dx[] = {0, -1, 0, 1};
int dy[] = {1, 0, -1, 0};
inline double calc(double x1, double y1, double x2, double y2) {
	return sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1));
}
inline bool isGood(long double gX, long double gY)
{	
	long double dist = 0;
	for(int i = 1; i <= N; i++) 
		dist += calc(p[i].x, p[i].y, gX, gY);
	if (dist < Sdist) {
		Sdist = dist;
		return 1;
	}
	return 0;
}
int main () {

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

	scanf("%d\n", &N);
	
	int i, k;
	long double gx = 0, gy = 0;

	for(i = 1; i <= N; i++) {
		scanf("%lf %lf\n", &p[i].x, &p[i].y);
		gx += p[i].x;
		gy += p[i].y;
	}
	gx /= N;
	gy /= N;
	
	isGood(gx, gy);
	for(double lim = 1025; lim > eps; ) {
		for(k = 0; k < 4; k++)
			if(isGood(gx + lim * dx[k], gy + lim * dy[k])) {
				gx += lim * dx[k];
				gy += lim * dy[k];
				break;
			}
		if (k == 4) lim /= 2.0;
	}
	printf("%.4Lf %.4Lf\n", gx, gy);
	return 0;
}