Cod sursa(job #1253840)

Utilizator vladrochianVlad Rochian vladrochian Data 1 noiembrie 2014 21:13:11
Problema Adapost 2 Scor 97
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <fstream>
#include <iomanip>
#include <cmath>
using namespace std;

const int kMaxN = 50005;

ifstream fin("adapost2.in");
ofstream fout("adapost2.out");

int N;
double px[kMaxN], py[kMaxN], dmin = 1000000006.9, step = 250.0, x, y;

inline double Dist(double x1, double y1, double x2, double y2) {
	double dx = x1 - x2, dy = y1 - y2;
	return sqrt(dx * dx + dy * dy);
}

bool Check(double nx, double ny) {
	double crt = 0.0;
	for (int i = 0; i < N; ++i)
		crt += Dist(nx, ny, px[i], py[i]);
	if (crt < dmin) {
		dmin = crt;
		x = nx;
		y = ny;
		return true;
	}
	return false;
}

int main() {
	fin >> N;
	for (int i = 0; i < N; ++i)
		fin >> px[i] >> py[i];
	Check(500.0, 500.0);
	int stmax = N < 10000 ? 75 : 30;
	for (int i = 0; i < stmax; ++i, step /= 2) {
		if (!Check(x + step, y))
			Check(x - step, y);
		if (!Check(x, y + step))
			Check(x, y - step);
	}
	fout << setprecision(4) << fixed << x << " " << y << "\n";
	return 0;
}