Cod sursa(job #1081545)

Utilizator BuseSorinFMI Buse Sorin-Marian BuseSorin Data 13 ianuarie 2014 18:38:27
Problema Adapost 2 Scor 81
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2013 Marime 1.04 kb
#include<iostream>
#include<fstream>
#include<math.h>
#include<iomanip>
#define dim 50006
using namespace std;


double x, y, Dabs, step;
int i, n;
struct {
	double x, y;
}v[dim];
inline double Dist(double x, double y){
	double s = 0.0;
	for (int i = 1; i <= n; ++i){
		s += sqrt((x - v[i].x)*(x - v[i].x) + (y - v[i].y)*(y - v[i].y));
	}
	return s;
}
int main() {

	ifstream f("adapost2.in");
	ofstream p("adapost2.out");

	f >> n;
	for (i = 1; i <= n; ++i) {
		f >> v[i].x >> v[i].y;
		x += v[i].x;
		y += v[i].y;
	}
	x /= n;
	y /= n;
	step = 200;
	Dabs = Dist(x, y);

	while (step>0.0001) {

		double dx[] = { step, -step, 0, 0 };
		double dy[] = { 0, 0, step, -step };
		bool ok = 1;
		double xa = 0.0;
		double ya = 0.0;
		double D = Dist(x, y);
		for (i = 0; i <= 3 && ok != 0; ++i){
			if (Dist(x + dx[i], y + dy[i])<Dabs){
				Dabs = Dist(x + dx[i], y + dy[i]);
				x = x + dx[i];
				y = y + dy[i];
				ok = 0;
			}
		}
		if (ok)
			step /= 2;
	}

	p<<setprecision(5) << x << " " << y;
	return 0;
}