Pagini recente » Cod sursa (job #2638120) | Cod sursa (job #2297939) | Cod sursa (job #1695502) | Cod sursa (job #1894222) | Cod sursa (job #2066296)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("adapost2.in");
ofstream fout("adapost2.out");
const int dx[] = {-1, -1, -1, 0, 1, 1, 1, 0};
const int dy[] = {-1, 0, 1, 1, 1, 0, -1, -1};
const int NMax = 5e4 + 50;
const double eps = 1e-4;
int n;
pair < double, double > points[NMax];
double power(const double &x) {
return x * x;
}
double pointsDistance(const pair < double, double > &a, const pair < double, double > &b) {
return sqrt(power(a.first - b.first) + power(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() {
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
fin >> n;
for(int i = 1; i <= n; ++i) fin >> 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;
int dir = -1;
pair < double, double > auxPair;
double auxDist, best;
double dist = allDistance(ans);
double hi = 1000.0;
while(hi >= 0.0000000001) {
dir = -1;
best = dist;
for(int d = 0; d < 8; ++d) {
auxPair = {ans.first + dx[d] * hi, ans.second + dy[d] * hi};
auxDist = allDistance(auxPair);
if(best > auxDist) {
best = auxDist;
dir = d;
}
}
if(dir != -1) {
ans.first += dx[dir] * hi;
ans.second += dy[dir] * hi;
}
hi /= 2.0;
}
fout << fixed << setprecision(4) << ans.first << " " << ans.second;
return 0;
}