Cod sursa(job #2499060)

Utilizator MoodyFaresFares Mohamad MoodyFares Data 25 noiembrie 2019 10:51:44
Problema Adapost 2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.86 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;
}

int minIndex;
double min_step_dist(Point p, double step) {
  double ans, temp;

  ans = sum_dist({p.x + step, p.y});
  minIndex = 1;

  temp = sum_dist({p.x - step, p.y});
  if (ans > temp) {
    ans = temp;
    minIndex = 2;
  }

  temp = sum_dist({p.x, p.y + step});
  if (ans > temp) {
    ans = temp;
    minIndex = 3;
  }

  temp = sum_dist({p.x, p.y - step});
  if (ans > temp) {
    ans = temp;
    minIndex = 4;
  }

  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;

  if (minIndex == 1) {
    p.x += step;
  } else if (minIndex == 2) {
    p.x -= step;
  } else if (minIndex == 3) {
    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;
}