Pagini recente » Cod sursa (job #1337672) | Cod sursa (job #1178396) | Cod sursa (job #1104118) | Cod sursa (job #245032) | Cod sursa (job #2079936)
#include <bits/stdc++.h>
using namespace std;
constexpr int MAX_COORDINATE = 1000;
constexpr 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;
};
inline point center_of_mass(const vector< point >& points) {
point center;
for (auto&& it : points) {
center.x += it.x;
center.y += it.y;
}
center.x /= points.size();
center.y /= points.size();
return center;
}
inline double fast_sqrt (double x) {
double g(1), ng;
while (true) {
ng = (x/g + g)/2;
if (g != ng) g = ng;
else if (g == ng) break;
}
return g;
}
inline double euclidian_distance(const point& first, const point& second) {
return fast_sqrt( (first.x - second.x)*(first.x - second.x) + (first.y - second.y)*(first.y - second.y) );
}
inline double evaluate(const point& center, const vector< point >& points) {
double res = 0;
for (auto&& it : points)
res += euclidian_distance(it, center);
return res;
}
inline void solve() {
size_t point_count;
cin >> point_count;
vector< point > points(point_count);
for (auto& it : points)
cin >> it.x >> it.y;
point best_point = center_of_mass(points);
double best_evaluation = evaluate(best_point, points);
for (double jump = MAX_COORDINATE; jump > EPS; jump /= 2) {
double candidate_evaluation = 1.0 * numeric_limits< int >::max();
point candidate_point;
for (int dir = 0; dir < 4; ++dir) {
point current_point(best_point.x + dx[dir]*jump, best_point.y + dy[dir]*jump);
double current_evaluation = evaluate(current_point, points);
if (current_evaluation < candidate_evaluation) {
candidate_evaluation = current_evaluation;
candidate_point = current_point;
}
}
if (candidate_evaluation < best_evaluation) {
best_evaluation = candidate_evaluation;
best_point = candidate_point;
jump *= 2;
}
}
cout << setprecision(4) << fixed << best_point.x << ' ' << best_point.y << endl;
}
int main() {
assert(freopen("adapost2.in", "r", stdin));
assert(freopen("adapost2.out", "w", stdout));
cin.tie(nullptr);
ios_base::sync_with_stdio(false);
solve();
return 0;
}