Pagini recente » Cod sursa (job #3250039) | Cod sursa (job #475867) | Cod sursa (job #2675174) | Cod sursa (job #197324) | Cod sursa (job #2066318)
#include <bits/stdc++.h>
using namespace std;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
const int NMax = 5e4 + 50;
const double eps = 1e-12;
int n;
pair < double, double > points[NMax];
double pointsDistance(const pair < double, double > &a, const pair < double, double > &b) {
return sqrt((a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second));
}
double allDistance(const pair < double, double > &x) {
double ret = (double)0.0;
for(int i = 1; i <= n; ++i) {
ret += pointsDistance(points[i], x);
}
return ret;
}
int main() {
freopen("adapost2.in", "r", stdin);
freopen("adapost2.out", "w", stdout);
scanf("%d", &n);
for(int i = 1; i <= n; ++i) scanf("%lf%lf", &points[i].first, &points[i].second);
pair < double, double > ans;
for(int i = 1; i <= n; ++i) {
ans.first += points[i].first;
ans.second += points[i].second;
}
ans.first /= (double)n;
ans.second /= (double)n;
pair < double, double > auxPair;
double auxDist;
double dist = allDistance(ans);
double hi = 1000.0;
while(hi >= 0.000001) {
for(int d = 0; d < 4; ++d) {
auxPair = {ans.first + dx[d] * hi, ans.second + dy[d] * hi};
auxDist = 0.0;
for(int i = 1; i <= n; ++i) {
auxDist += pointsDistance(points[i], auxPair);
}
if(abs(dist - auxDist) < eps) continue;
if(dist > auxDist) {
dist = auxDist;
ans = auxPair;
d = -1;
}
}
hi /= 2.0;
}
printf("%.4lf %.4lf", ans.first, ans.second);
return 0;
}