Cod sursa(job #3992)

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



struct point {double x, y;};
int N, i, j;
point v[50100];
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 XX, double dist) {
	double best = -1;
	int i, p= -1 ;
	best = 0;
		for (i=0; i<N; i++){
			double d1 = XX.x - v[i].x, d2 = XX.y - v[i].y;
			best+=d1*d1+d2*d2;
			}
	for (int d =0; d<4; d++) {
		point Y = XX;
		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 (best==-1 || A < best) {best = A; p = d;}
		}
	if (p!=-1){
	XX.x+=di[p]*dist;
	XX.y+=dj[p]*dist;}
	return XX;
	}
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;
//	printf("%lf %lf\n", X.x, X.y);
        X.x = 0;
        X.y = 0;
	double dist = 2000;
	for (int k = 1; k<=200; k++) {
		dist = dist/2.0;
//                for (int j = 1; j<=10; j++)
		X = apropie(X, dist);
		}
	printf("%lf %lf\n", X.x, X.y);
	return 0;
}