Pagini recente » Cod sursa (job #1695481) | Cod sursa (job #983482) | Cod sursa (job #1381094) | Sandbox (cutiuţa cu năsip) | Cod sursa (job #2066376)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("adapost2.in");
ofstream fout("adapost2.out");
typedef pair < double, double > var;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
double power(const double &x) {
return x * x;
}
double pointDistance(const var &a, const var &b) {
return sqrt(power(a.first - b.first) + power(a.second - b.second));
}
double allDistance(const vector < var > &data, const var &x) {
double ret = 0.0;
for(auto it: data) {
ret += pointDistance(it, x);
}
return ret;
}
double obt[4];
int main() {
int n;
fin >> n;
vector < var > data(n);
for(auto &it: data) {
fin >> it.first >> it.second;
}
var ans = {0, 0};
for(auto it: data) {
ans.first += it.first;
ans.second += it.second;
}
ans.first /= (double) n;
ans.second /= (double) n;
double len = allDistance(data, ans);
double dist = 1000.0;
while(dist >= 0.0000001) {
for(int d = 0; d < 4; ++d) {
var aux = {ans.first + dx[d] * dist, ans.second + dy[d] * dist};
obt[d] = allDistance(data, aux);
}
double m = obt[0];
int p = 0;
for(int d = 1; d < 4; ++d) {
if(obt[d] < m) {
m = obt[d];
p = d;
}
}
if(m < len) {
len = m;
ans = {ans.first + dx[p] * dist, ans.second + dy[p] * dist};
} else {
dist *= 0.5;
}
}
fout << fixed << setprecision(4) << ans.first << " " << ans.second;
return 0;
}