Cod sursa(job #750625)

Utilizator valentin.harsanValentin Harsan valentin.harsan Data 22 mai 2012 18:32:33
Problema Adapost 2 Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 kb
#include<iostream>
#include<fstream>
#include<cmath>
using namespace std;

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

#define N 50010

const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};

int n;
double x[N], y[N], px, py, dmin = 1000000000, t;

inline double dist(double pozx, double pozy) {
	int i;
	double rez = 0;
	
	for(i = 1; i<=n; ++i)
		rez += sqrt((pozx - x[i]) * (pozx - x[i]) + (pozy - y[i]) * (pozy - y[i]));
	
	return rez;
}

int main() {
	int i, j;
	double pas = 512;
	
	in >> n;
	
	for(i = 1; i<=n; ++i)
		in >> x[i] >> y[i], px += x[i], py += y[i];
	
	px/=n; py/=n;
	
	for(i = 1; i<=43; pas/=2, ++i) 
		for(j = 0; j!=4; ++j) {
			t = dist(px + pas*dx[j], py + pas*dy[j]);
			
			if(t < dmin) {
				dmin = t;
				
				px += pas*dx[j];
				py += pas*dy[j];
				pas*=2;
				break;
			}
		}
	
	out << px << " " << py << "\n";
	
	return 0;
}