Pagini recente » Cod sursa (job #2441303) | Cod sursa (job #3154380) | Cod sursa (job #1122868) | Cod sursa (job #1215449) | Cod sursa (job #2082614)
#include <algorithm>
#include <fstream>
#include <cmath>
#include <iostream>
#include <iomanip>
#include <vector>
using namespace std;
int main() {
ifstream fin("adapost2.in");
ofstream fout("adapost2.out");
int n;
fin >> n;
vector<double> x(n);
vector<double> y(n);
double cx = 0, cy = 0;
for (int i = 0; i < n; ++i) {
fin >> x[i] >> y[i];
cx += x[i];
cy += y[i];
}
cx /= n; cy /= n;
auto getValue = [&](double vx, double vy) -> double {
double ans = 0;
for (int i = 0; i < n; ++i) {
ans += sqrt((vx - x[i]) * (vx - x[i]) + (vy - y[i]) * (vy - y[i]));
}
return ans;
};
const int dx[] = {-1, -1, 0, 1, 1, 0};
const int dy[] = {0, 1, 1, 0, -1, -1};
double coef = 300;
double dist = getValue(cx, cy);
int lim = 23;
if (n <= 10000) {
lim = 40;
}
for (int it = 0; it < lim; ++it) {
int dir = -1;
double minDist = 1e99;
for (int i = 0; i < 6; ++i) {
double nx = cx + dx[i] * coef;
double ny = cy + dy[i] * coef;
double cDist = getValue(nx, ny);
if (cDist < minDist) {
minDist = cDist;
dir = i;
}
}
if (minDist < dist) {
dist = minDist;
cx += dx[dir] * coef;
cy += dy[dir] * coef;
}
coef *= 0.6;
}
fout << setprecision(4) << fixed;
fout << cx << ' ' << cy << '\n';
fin.close();
fout.close();
}