Cod sursa(job #3989)

Utilizator vlad_DVlad Dumitriu vlad_D Data 29 decembrie 2006 23:22:55
Problema Adapost 2 Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <stdio.h>
#include <algorithm>

using namespace std;

struct point {double x, y;};
int N, i, j;
point v[50010];
point X;
double di[] = {-1, 0, 1, 0, -1, 1, 1, -1};
double dj[] = {0, 1, 0 , -1, 1, 1, -1, -1};
point apropie(point X, double dist) {
	double best = -1;
	int i, p= -1 ;
	best = 0;
		for (i=0; i<N; i++){
			double d1 = X.x - v[i].x, d2 = X.y - v[i].y;
			best+=d1*d1+d2*d2;
			}
	for (int d =0; d<4; d++) {
		point Y = X;
		Y.x+=di[d]*dist;
		Y.y+=dj[d]*dist;
		double A = 0;
		for (i=0; i<N; i++){
			double d1 = Y.x - v[i].x, d2 = Y.y - v[i].y;
			A+=d1*d1+d2*d2;
			}
		if (A < best) {best = A; p = d;}
		}
	if (p!=-1){
	X.x+=di[p]*dist;
	X.y+=dj[p]*dist;}
	return X;
	}
int main() {
	freopen("adapost2.in", "r", stdin);
	freopen("adapost2.out", "w", stdout);
	scanf("%d", &N);
	for (i=0; i<N; i++) scanf("%lf %lf", &(v[i].x), &(v[i].y));
	for (i=0; i<N; i++) X.x+=v[i].x, X.y+=v[i].y;
	X.x/=1.*N;
	X.y/=1.*N;
	double dist = 2;
	for (int k = 1; k<=20; k++) {
		dist = dist/2.0;
		X = apropie(X, dist);
		}
	printf("%lf %lf\n", X.x, X.y);
	return 0;
}