Cod sursa(job #2377884)

Utilizator Constantin.Dragancea Constantin Constantin. Data 11 martie 2019 12:57:53
Problema Adapost 2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <bits/stdc++.h>
using namespace std;
typedef long double ld;

int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
const ld eps = 0.00005;
const int N = 50010;
struct point{
    ld x, y;
} a[N];
int n;
ld step = 1000, mn = 1e9, x, y;

ld dist(double i3, double j3){
    ld rs = 0;
    for (int i=1; i<=n; i++) rs += sqrt((a[i].x-i3)*(a[i].x-i3) + (a[i].y-j3)*(a[i].y-j3));
    return rs;
}

int main(){
    ifstream cin ("adapost2.in");
    ofstream cout ("adapost2.out");
    cin >> n;
    for (int i=1; i<=n; i++) cin >> a[i].x >> a[i].y, x += a[i].x, y += a[i].y;
    x /= n; y /= n;
    while (step > eps){
        for (int dir=0; dir<4; dir++){
            double i2 = x + step*dx[dir], j2 = y + step*dy[dir];
            double t = dist(i2, j2);
            if (t < mn) x = i2, y = j2, mn = t;
        }
        step /= 2;
    }
    cout << fixed << setprecision(4) << x +199<< " " << y+199;
    return 0;
}