Pagini recente » Cod sursa (job #462842) | Cod sursa (job #2215987) | Cod sursa (job #1511614) | Cod sursa (job #2015383) | Cod sursa (job #2499059)
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const int MAX_N = 50000;
const double eps = 1.e-3;
struct Point {
double x;
double y;
};
int n;
Point points[1 + MAX_N];
double dist(Point a, Point b) {
return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
double sum_dist(Point p) {
double s = 0.;
for (int i = 1; i <= n; i++)
s += dist(p, points[i]);
return s;
}
double min_step_dist(Point p, double step) {
double ans;
ans = sum_dist({p.x + step, p.y});
ans = min(ans, sum_dist({p.x - step, p.y}));
ans = min(ans, sum_dist({p.x, p.y + step}));
ans = min(ans, sum_dist({p.x, p.y - step}));
return ans;
}
Point find_point(Point p, double step) {
while (step > eps && min_step_dist(p, step) > sum_dist(p)) {
step /= 2;
}
if (step <= eps)
return p;
double minDist = min_step_dist(p, step);
if (sum_dist({p.x + step, p.y}) == minDist) {
p.x += step;
} else if (sum_dist({p.x - step, p.y}) == minDist) {
p.x -= step;
} else if (sum_dist({p.x, p.y + step}) == minDist) {
p.y += step;
} else {
p.y -= step;
}
return find_point(p, step);
}
int main() {
freopen("adapost2.in", "r", stdin);
freopen("adapost2.out", "w", stdout);
scanf("%d", &n);
Point ll, tr;
ll = {1000., 1000.};
tr = {0., 0.};
for (int i = 1; i <= n; i++) {
double x, y;
scanf("%lf%lf", &x, &y);
points[i] = {x, y};
ll.x = min(ll.x, x);
ll.y = min(ll.y, y);
tr.x = max(tr.x, x);
tr.y = max(tr.y, y);
}
Point p, ans;
p.x = (ll.x + tr.x) / 2;
p.y = (ll.y + tr.y) / 2;
ans = find_point(p, max(tr.x - ll.x, tr.y - ll.y) / 2);
printf("%.4lf %.4lf\n", ans.x, ans.y);
return 0;
}