Pagini recente » Cod sursa (job #307341) | Cod sursa (job #107407) | Cod sursa (job #705457) | Cod sursa (job #2161599) | Cod sursa (job #2082623)
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <algorithm>
#include <fstream>
#include <cmath>
#include <iostream>
#include <iomanip>
#include <vector>
using namespace std;
double x[50011];
double y[50011];
int main() {
ifstream fin("adapost2.in");
ofstream fout("adapost2.out");
int n;
fin >> n;
int m = n;
if (n % 4 != 0) {
m -= m % 4;
m += 4;
}
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 = [n, m](double vx, double vy) -> double {
double ans = 0;
for (int i = n; i < m; ++i) {
x[i] = vx;
y[i] = vy;
}
for (int i = 0; i < n; i += 4) {
ans += sqrt((vx - x[i]) * (vx - x[i]) + (vy - y[i]) * (vy - y[i]));
ans += sqrt((vx - x[i + 1]) * (vx - x[i + 1]) + (vy - y[i + 1]) * (vy - y[i + 1]));
ans += sqrt((vx - x[i + 2]) * (vx - x[i + 2]) + (vy - y[i + 2]) * (vy - y[i + 2]));
ans += sqrt((vx - x[i + 3]) * (vx - x[i + 3]) + (vy - y[i + 3]) * (vy - y[i + 3]));
}
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 = 30;
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();
}