Cod sursa(job #329211)

Utilizator Magnuscont cu nume gresit sau fals Magnus Data 5 iulie 2009 12:14:06
Problema Adapost 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <cstdio>
#include <cmath>

const int maxn = 50001;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
const double eps = 0.001;

FILE *in = fopen("adapost2.in","r"), *out = fopen("adapost2.out","w");

struct punct
{
 double x, y;
};

int n;
punct a[maxn];
double x, y;

double dist(double x, double y)
{
 double ret = 0;
 for ( int i = 1; i <= n; ++i )
 {
  double dx = a[i].x - x;
  double dy = a[i].y - y;
  ret += sqrt(dx*dx + dy*dy);
 }
 return ret;
}

int main()
{
 fscanf(in, "%d", &n);
 for ( int i = 1; i <= n; ++i )
  fscanf(in, "%lf %lf", &a[i].x, &a[i].y),
 x += a[i].x,
 y += a[i].y;
 x /= n;
 y /= n;
 double d = dist(x, y);
 double step = 100.0;
 int done = 0;
 while ( step > eps )
 {
  done = 0;
  for ( int i = 0; i < 4; ++i )
  {
   double nx = (double)x + step*dx[i];
   double ny = (double)y + step*dy[i];
   double t = dist(nx, ny);
   if ( t < d )
   {
    d = t;
    x = nx;
    y = ny;
    done = 1;
    break;
   }
  }
  if ( !done ) step /= 2;
 }
 fprintf(out, "%.4lf %.4lf\n", x, y);
 return 0;
}