Pagini recente » Cod sursa (job #143802) | Cod sursa (job #923872) | Cod sursa (job #56175) | Cod sursa (job #1162111) | Cod sursa (job #1669352)
#include <cstdio>
#include <cmath>
using namespace std;
const int N = 50002;
const double eps = 1.e-14;
struct Point {
double x, y;
};
int n;
Point P [N];
double dist (const Point &A, const Point &B) {
return sqrt ((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y));
}
double solve (const Point &G) {
int i;
double ans = 0;
for (i = 1; i <= n; i ++)
ans += dist (G, P [i]);
return ans;
}
int main () {
int i;
double pas = 100, d1, d2, d3, d4, ans, d;
Point G, Gn, G1, G2, G3, G4;
freopen ("adapost2.in", "r", stdin);
freopen ("adapost2.out", "w", stdout);
scanf ("%d", &n);
G.x = G.y = 0;
for (i = 1; i <= n; i ++) {
scanf ("%lf%lf", &P [i].x, & P [i].y);
G.x += P [i].x;
G.y += P [i].y;
}
G.x = G.x / n;
G.y = G.y / n;
d = solve (G);
for (i = 1; i <= 40; i ++) {
G1 = G2 = G3 = G4 = G;
G1.x += pas;
G2.y += pas;
G3.x -= pas;
G4.y -= pas;
d1 = solve (G1);
d2 = solve (G2);
d3 = solve (G3);
d4 = solve (G4);
ans = d1; Gn = G1;
if (d2 - ans <= -eps) {
ans = d2;
Gn = G2;
}
if (d3 - ans <= -eps) {
ans = d3;
Gn = G3;
}
if (d4 - ans <= -eps) {
ans = d4;
Gn = G4;
}
if (ans - d <= -eps) {
G = Gn;
d = ans;
}
else
pas = pas / 2;
}
printf ("%f %f\n", G.x, G.y);
return 0;
}