Cod sursa(job #1862428)

Utilizator iordache.bogdanIordache Ioan-Bogdan iordache.bogdan Data 29 ianuarie 2017 22:22:35
Problema Adapost 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.9 kb
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <limits>
#include <iomanip>

const int kMaxDim = 50005;
const int kMaxCoordinate = 1000;
const double eps = 1e-4;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, -1, 1};

struct Point {
	Point(double _x = 0, double _y = 0) :
		x(_x),
		y(_y) {
	}

	double x, y;
};

int pointCount;
Point points[kMaxDim];

inline double Distance(const Point& a, const Point& b) {
	return std::sqrt( (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y) );
}

inline Point CenterOfGravity(Point points[], int pointCount) {
	Point center(0, 0);
	for (int i = 0; i < pointCount; ++i) {
		center.x += points[i].x;
		center.y += points[i].y;
	}
	center.x /= pointCount;
	center.y /= pointCount;
	return center;
}

inline double Evaluate(const Point& point) {
	double res = 0;
	for (int i = 0; i < pointCount; ++i)
		res += Distance(point, points[i]);
	return res;
}

int main() {
	freopen("adapost2.in", "r", stdin);
	freopen("adapost2.out", "w", stdout);

	scanf("%d", &pointCount);
	for (int i = 0; i < pointCount; ++i)
		scanf("%lf %lf", &points[i].x, &points[i].y);

	Point bestPoint = CenterOfGravity(points, pointCount);
	double bestValue = Evaluate(bestPoint);

	for (double jump = kMaxCoordinate; jump > eps; jump /= 2) {
		double candidateValue = 1.0 * std::numeric_limits< int >::max();
		Point candidatePoint;
		for (int dir = 0; dir < 4; ++dir) {
			Point temp(bestPoint.x + dx[dir]*jump, bestPoint.y + dy[dir]*jump);
			double currValue = Evaluate(temp);
			if (currValue < candidateValue) {
				candidateValue = currValue;
				candidatePoint = temp;
			}
		}

		if (candidateValue < bestValue) {
			bestPoint = candidatePoint;
			bestValue = candidateValue;
			jump *= 2;
		}
	}

	printf("%.4lf %.4lf\n", bestPoint.x, bestPoint.y);

	return 0;
}

//Trust me, I'm the Doctor!