Pagini recente » Cod sursa (job #2874508) | Cod sursa (job #1211469) | Cod sursa (job #1102346) | Cod sursa (job #1694598) | Cod sursa (job #2082600)
#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 minx = 1000, maxx = -1000, miny = 1000, maxy = -1000;
for (int i = 0; i < n; ++i) {
fin >> x[i] >> y[i];
minx = min(minx, x[i]);
maxx = max(maxx, x[i]);
miny = min(miny, y[i]);
maxy = max(maxy, y[i]);
}
auto getValue = [&](double cx, double cy) -> double {
double ans = 0;
for (int i = 0; i < n; ++i) {
ans += sqrt((cx - x[i]) * (cx - x[i]) + (cy - y[i]) * (cy - y[i]));
}
return ans;
};
auto searchX = [&](double y) -> pair<double, double> {
double lx = minx, rx = maxx;
for (int it = 0; it < 40; ++it) {
double v1 = getValue((2 * lx + rx) / 3, y);
double v2 = getValue((lx + 2 * rx) / 3, y);
if (v1 < v2) {
rx = (lx + 2 * rx) / 3;
} else {
lx = (2 * lx + rx) / 3;
}
}
return make_pair((lx + rx) * 0.5, getValue((lx + rx) * 0.5, y));
};
double ly = miny, ry = maxy;
for (int i = 0; i < 40; ++i) {
double v1 = searchX((2 * ly + ry) / 3).second;
double v2 = searchX((ly + 2 * ry) / 3).second;
if (v1 < v2) {
ry = (ly + 2 * ry) / 3;
} else {
ly = (2 * ly + ry) / 3;
}
}
double ansx = searchX((ly + ry) * 0.5).first;
double ansy = (ly + ry) * 0.5;
fout << setprecision(4) << fixed;
fout << ansx << ' ' << ansy << '\n';
fin.close();
fout.close();
}