Pagini recente » Cod sursa (job #1481430) | Cod sursa (job #1076030) | Cod sursa (job #436983) | Cod sursa (job #1880471) | Cod sursa (job #1862428)
#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!