Cod sursa(job #2066395)

Utilizator eu3neuomManghiuc Teodor-Florin eu3neuom Data 14 noiembrie 2017 22:58:38
Problema Adapost 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.69 kb
#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() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
     
    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(dist > auxDist) {
                dist = auxDist;
                ans = auxPair;
            }
        }
 
        hi *= 0.6;
    }
 
    printf("%.4lf %.4lf", ans.first, ans.second);
    return 0;
}