Cod sursa(job #1081214)

Utilizator vld7Campeanu Vlad vld7 Data 13 ianuarie 2014 12:57:12
Problema Adapost 2 Scor 100
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2013 Marime 1.26 kb
#include <fstream>
#include <iomanip>
#include <cmath>
#include <vector>

using namespace std;

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

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

int n;
double ansx, ansy, ansSum;
vector < pair <double, double> > Point;

double get_dist (double x1, double y1, double x2, double y2) {
	double tmp1 = x2 - x1;
	double tmp2 = y2 - y1;
	
	return sqrt (tmp1 * tmp1 + tmp2 * tmp2);
}

double get_sum (double x, double y) {
	double ret = 0;
	for (int i = 0; i < n; i++) {
		ret += get_dist (x, y, Point[i].first, Point[i].second);
	}
	
	return ret;
}

int main() {
	f >> n;
	for (int i = 1; i <= n; i++) {
		double tmp1, tmp2;
		f >> tmp1 >> tmp2;
		Point.push_back (make_pair (tmp1, tmp2));
	}
	
	ansx = 0;
	ansy = 0;
	ansSum = get_sum (ansx, ansy);
	
	double step = 1000;
	while (step > 0.001) {
		for (int k = 0; k < 4; k++) {
			double newx = ansx + dx[k] * step;
			double newy = ansy + dy[k] * step;
			
			double crt_sum = get_sum (newx, newy);
			if (crt_sum < ansSum) {
				ansx = newx;
				ansy = newy;
				ansSum = crt_sum;
				step *= 2;
				break;
			}
		}
		step /= 2;
	}
	
	g << fixed << setprecision(4) << ansx << " " << ansy;
	
	return 0;
}