Cod sursa(job #1968706)

Utilizator MiricaMateiMirica Matei MiricaMatei Data 17 aprilie 2017 20:10:20
Problema Adapost 2 Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <cstdio>
#include <cmath>
using namespace std;
struct Point{
  double x, y;
};
Point v[50005];
int dx[] = {-1, -1, -1, 0, 1, 1, 1, 0};
int dy[] = {-1, 0, 1, 1, 1, 0, -1, -1};
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 getDist(Point c, int n){
  double d = 0;
  for (int i = 1; i <= n; ++i)
    d += dist(c, v[i]);
  return d;
}
Point adun(Point a, int i, double pas){
  return {a.x + dx[i] * pas, a.y + dy[i] * pas};
}
int main(){
  freopen("adapost2.in", "r", stdin);
  freopen("adapost2.out", "w", stdout);
  int n;
  scanf("%d", &n);
  Point ans = {0, 0};
  for (int i = 1; i <= n; ++i){
    scanf("%lf%lf", &v[i].x, &v[i].y);
    ans.x += v[i].x;
    ans.y += v[i].y;
  }
  ans.x /= (double)n;
  ans.y /= (double)n;
  double pas = 1000;
  while (pas > 1.e-4){
    double minim = getDist(ans, n), index = -1;
    for (int i = 0; i < 8; ++i){
      double distanta = getDist(adun(ans, i, pas), n);
      if (distanta < minim){
        minim = distanta;
        index = i;
      }
    }
    if (index == -1)
      pas = pas / 2;
    else
      ans = adun(ans, index, pas);
  }
  printf("%.4f %.4f\n", ans.x, ans.y);
  return 0;
}