Cod sursa(job #2499059)

Utilizator MoodyFaresFares Mohamad MoodyFares Data 25 noiembrie 2019 10:50:56
Problema Adapost 2 Scor 85
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.78 kb
#include <cstdio>
#include <algorithm>
#include <cmath>

using namespace std;

const int MAX_N = 50000;
const double eps = 1.e-3;

struct Point {
  double x;
  double y;
};

int n;
Point points[1 + MAX_N];

double dist(Point a, Point b) {
  return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

double sum_dist(Point p) {
  double s = 0.;
  for (int i = 1; i <= n; i++)
    s += dist(p, points[i]);
  return s;
}

double min_step_dist(Point p, double step) {
  double ans;

  ans = sum_dist({p.x + step, p.y});
  ans = min(ans, sum_dist({p.x - step, p.y}));
  ans = min(ans, sum_dist({p.x, p.y + step}));
  ans = min(ans, sum_dist({p.x, p.y - step}));

  return ans;
}

Point find_point(Point p, double step) {
  while (step > eps && min_step_dist(p, step) > sum_dist(p)) {
    step /= 2;
  }

  if (step <= eps)
    return p;

  double minDist = min_step_dist(p, step);
  if (sum_dist({p.x + step, p.y}) == minDist) {
    p.x += step;
  } else if (sum_dist({p.x - step, p.y}) == minDist) {
    p.x -= step;
  } else if (sum_dist({p.x, p.y + step}) == minDist) {
    p.y += step;
  } else {
    p.y -= step;
  }

  return find_point(p, step);
}

int main() {
  freopen("adapost2.in", "r", stdin);
  freopen("adapost2.out", "w", stdout);


  scanf("%d", &n);

  Point ll, tr;

  ll = {1000., 1000.};
  tr = {0., 0.};
  for (int i = 1; i <= n; i++) {
    double x, y;

    scanf("%lf%lf", &x, &y);
    points[i] = {x, y};

    ll.x = min(ll.x, x);
    ll.y = min(ll.y, y);

    tr.x = max(tr.x, x);
    tr.y = max(tr.y, y);
  }

  Point p, ans;

  p.x = (ll.x + tr.x) / 2;
  p.y = (ll.y + tr.y) / 2;
  ans = find_point(p, max(tr.x - ll.x, tr.y - ll.y) / 2);


  printf("%.4lf %.4lf\n", ans.x, ans.y);
  return 0;
}