Cod sursa(job #1991920)

Utilizator DjokValeriu Motroi Djok Data 18 iunie 2017 18:27:38
Problema Adapost 2 Scor 70
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2013 Marime 1.2 kb
#include <bits/stdc++.h>
using namespace std;

struct point {
  double x, y;

  point(double _x = 0, double _y = 0) { x = _x; y = _y; }

  double dist(point b) {
    double dx = x - b.x;
    double dy = y - b.y;
    return sqrt(dx * dx + dy * dy);
  }
};

const int N = 50005;
const double EPS = 1e-4;

int i, n;
double dev = 500, dist, rs;
point a[N], ans(500, 500);

double getDist(point p) {
  double ans = 0;
  for(int i = 1; i <= n; ++i) ans += p.dist(a[i]);

  return ans;
}

int main() {
  ifstream cin("adapost2.in");
  ofstream cout("adapost2.out");
  ios_base::sync_with_stdio(0);

  cin >> n;
  for(i = 1; i <= n; ++i) cin >> a[i].x >> a[i].y;

  rs = getDist(ans);
  while(dev >= EPS) {
    for(i = 0; i < 15; ++i) {
      if((dist = getDist(point(ans.x - dev, ans.y))) < rs) rs = dist, ans.x -= dev;
      if((dist = getDist(point(ans.x, ans.y + dev))) < rs) rs = dist, ans.y += dev;
      if((dist = getDist(point(ans.x, ans.y - dev))) < rs) rs = dist, ans.y -= dev;
      if((dist = getDist(point(ans.x + dev, ans.y))) < rs) rs = dist, ans.x += dev;
    }
    dev /= 2;
  }

  cout << setprecision(3) << fixed << ans.x << ' ' << ans.y << '\n';

  return 0;
}