Pagini recente » Istoria paginii utilizator/vasiliu_cris | Profil salam.boss | Profil elituni | Profil ionutz_yo | Cod sursa (job #2070525)
#include <bits/stdc++.h>
using namespace std;
ifstream in("adapost2.in");
ofstream out("adapost2.out");
struct lol{
double x, y;
};
int n;
double u, d, l, r, x, y, eps = 100, bst;
lol a[50100];
double dist(lol a, lol b){
return sqrt((b.x - a.x) * (b.x - a.x) + (b.y - a.y) * (b.y - a.y));
}
double get(lol p){
double s = 0;
for(int i = 1; i <= n; i++)
s += dist(p, a[i]);
return s;
}
int main(){
in >> n;
for(int i = 1; i <= n; i++){
in >> a[i].x >> a[i].y;
x += a[i].x;
y += a[i].y;
}
x /= n; y /= n;
bst = get({x, y});
for(int i = 1; i <= 40; i++, eps /= 1.5){
u = get({x - eps, y});
d = get({x + eps, y});
l = get({x, y - eps});
r = get({x, y + eps});
if(u < min({bst, d, l, r})){
bst = u;
x -= eps;
continue;
}
if(d < min({bst, u, l, r})){
bst = d;
x += eps;
continue;
}
if(l < min({bst, u, d, r})){
bst = l;
y -= eps;
continue;
}
if(r < min({bst, u, d, l})){
bst = r;
y += eps;
continue;
}
}
out << fixed << setprecision(5) << x << ' ' << y;
return 0;
}