Cod sursa(job #328952)

Utilizator cotofanaCotofana Cristian cotofana Data 4 iulie 2009 02:12:16
Problema Adapost 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 kb
#include <stdio.h>
#include <math.h>
#define dim 50001
#define eps 0.00001

int n;
double x[dim], y[dim], xs, ys;

double calc_dist(double xx, double yy) {
	double dist=0.0;
	int i;
	
	for (i=1; i<=n; ++i)
		dist+=sqrt((xx-x[i])*(xx-x[i])+(yy-y[i])*(yy-y[i]));
	
	return dist;
}

void simulated_annealing() {
	const int dx[]={0, 1, 0, -1}, dy[]={1, 0, -1, 0};
	int i, ok;
	double xt, yt, offset=1000.0, dist;
	
	xs=ys=0;
	/*for (i=1; i<=n; ++i) xs+=x[i], ys+=y[i];
	xs/=n, ys/=n;*/
	dist=calc_dist(xs, ys);
	
	while (offset>eps) {
		ok=1;
		while (ok) {
			ok=0;
			for (i=0; i<=3; ++i) {
				xt=xs+offset*(double)dx[i];
				yt=ys+offset*(double)dy[i];
				if (calc_dist(xt, yt)<dist) {
					dist=calc_dist(xt, yt);
					xs=xt, ys=yt;
					ok=1;
				}
			}
		}
		offset/=10;
	}
}

int main() {
	int i;
	freopen("adapost2.in", "r", stdin);
	freopen("adapost2.out", "w", stdout);
	
	scanf("%d\n", &n);
	for (i=1; i<=n; ++i) scanf("%lf %lf\n", &x[i], &y[i]);
	
	simulated_annealing();
	
	printf("%.4lf %.4lf\n", xs, ys);
	
	return 0;
}