Cod sursa(job #493088)

Utilizator dornescuvladVlad Eugen Dornescu dornescuvlad Data 16 octombrie 2010 23:55:53
Problema Adapost 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.72 kb
#include <iostream>
#include <fstream>
#include <math.h>
#define  nmax 50006
#define  EPS 0.000001

using namespace std;

const char iname[] = "adapost2.in";
const char oname[] = "adapost2.out";

ifstream fin(iname);
ofstream fout(oname);

struct point
{
	double x, y;
}P[nmax], greutate, L, M, Q, D;
	
int N, i, j, k;
double sum, sumx, sumy, valoare = 1000.4, minimal = 1000000;

double calc_dist(point A, point B)
{
	return sqrt((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y));
}

double calc_all_dist(point A)
{	
	int i;
	sum = 0;
	for(i = 1; i <= N; i ++)
		sum = sum + calc_dist(P[i], A);
	return sum;
}

void calculate(point K)
{
	if(fabs(valoare - EPS) < 0.000001)
	{

		fout << K.x << " " << K.y;
		exit(0);
	}
	else
	{
		double normal = calc_all_dist(K);
		L.x = K.x - valoare;
		L.y = K.y;
		M.x = K.x + valoare;
		M.y = K.y;
		D.x = K.x;
		D.y = K.y - valoare;
		Q.x = K.x;
		Q.y = K.y + valoare;
		double stanga = calc_all_dist(L);
		double dreapta = calc_all_dist(M);
		double jos = calc_all_dist(D);
		double sus =  calc_all_dist(Q);
		
		minimal = min(min(dreapta, stanga), min(min(sus, jos), normal));
		if(fabs(minimal - normal) < EPS)
		{
			valoare = valoare / 2;
			calculate(K);
		}
		if(fabs(minimal - stanga) < EPS)
			calculate(L);
		else
			if(fabs(minimal - dreapta) < EPS)
				calculate(M);
			else
				if(fabs(minimal - jos) < EPS)
					calculate(D);
				else
					calculate(Q);
	}
}
		
	
int main()
{
	fin >> N;
	for(i = 1; i <= N; i ++)
	{
		fin >> P[i].x >> P[i].y;
		sumx = sumx + P[i].x;
		sumy = sumy + P[i].y;
	}
	
	sumx = sumx / N;
	sumy = sumy / N;
	greutate.x = sumx, greutate.y = sumy;
	calculate(greutate);
	return 0;
}