Pagini recente » Cod sursa (job #1150123) | Cod sursa (job #1171716) | Cod sursa (job #1217226) | Cod sursa (job #1477219) | Cod sursa (job #1541154)
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 50000;
const double EPS = 1e-8;
const int D[4][2] = { {-1, 0}, {0, 1}, {1, 0}, {0, -1} };
struct Point {
double x, y;
};
Point v[MAX_N];
double sumDistance(const Point &A, const int &N) {
double s = 0.00;
for (int i = 0; i < N; i++) {
s += sqrt((A.x - v[i].x) * (A.x - v[i].x) + (A.y - v[i].y) * (A.y - v[i].y));
}
return s;
}
int main(void) {
freopen("adapost2.in", "r", stdin);
freopen("adapost2.out", "w", stdout);
int N;
Point solution;
scanf("%d", &N);
solution.x = 0.00;
solution.y = 0.00;
for (int i = 0; i < N; i++) {
scanf("%lf%lf", &v[i].x, &v[i].y);
solution.x += v[i].x;
solution.y += v[i].y;
}
solution.x /= N;
solution.y /= N;
fclose(stdin);
double step = 256.00;
double solDist = sumDistance(solution, N);
int indx[4] = {0, 1, 2, 3};
while (step > EPS) {
double x = solution.x;
double y = solution.y;
double newStep = step * 0.5;
random_shuffle(indx, indx + 4);
for (int i = 0; i < 4; i++) {
Point tmp = {x + step * D[indx[i]][0], y + step * D[indx[i]][1]};
double d = sumDistance(tmp, N);
if (d < solDist) {
solDist = d;
solution = tmp;
newStep = step;
}
}
step = newStep;
}
printf("%.4f %.4f\n", solution.x, solution.y);
fclose(stdout);
return 0;
}