Pagini recente » Cod sursa (job #29793) | Cod sursa (job #443180) | Cod sursa (job #380120) | Cod sursa (job #2243522) | Cod sursa (job #1862423)
#include <fstream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <limits>
#include <iomanip>
const int kMaxDim = 50005;
const int kMaxCoordinate = 1000;
const double eps = 1e-5;
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() {
std::ifstream inputFile("adapost2.in");
std::ofstream outputFile("adapost2.out");
inputFile >> pointCount;
for (int i = 0; i < pointCount; ++i)
inputFile >> 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;
}
}
outputFile << std::setprecision(4) << std::fixed << bestPoint.x << ' ' << bestPoint.y << '\n';
inputFile.close();
outputFile.close();
return 0;
}
//Trust me, I'm the Doctor!