Cod sursa(job #130473)

Utilizator RobytzzaIonescu Robert Marius Robytzza Data 1 februarie 2008 12:07:48
Problema Adapost 2 Scor 61
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <fstream.h>
#include <math.h>

double x,y,a[50005],b[50005];
double Smin;
long n;
const int l[5]={-1,0,0,1};
const int c[5]={0,-1,1,0};

ifstream fin ("adapost2.in");
ofstream fout("adapost2.out");

void citire()
{
   fin>>n;
   for (int i=0;i<n;i++)
      fin>>a[i]>>b[i];
}

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

void f ()
{
double d=100;
while (d>=0.00005)
{
   double x1=x,y1=y,S;
   for (int k=0;k<4;k++)
   {
       S=0;
       for (int i=0;i<n;i++)
	   S+=dist (x1+l[k]*d,y1+c[k]*d,a[i],b[i]);
       if (S<Smin)
       {
	  Smin=S;
	  x=x1+l[k]*d;
	  y=y1+c[k]*d;
       }
   }
   if (x1==x && y1==y)
       d/=2;
  }
}

int main ()
{
   citire();
   Smin=10000000;
   for (int i=0;i<n;i++)
   {
       x+=a[i];
       y+=b[i];
   }
   x/=n;
   y/=n;
   f();
   long x1=10000*x,y1=10000*y;
   fout<<x1/10000<<"."<<x1%10000;
   fout<<" "<<y1/10000<<"."<<y1%10000<<"\n";
   fout.close();
   fin.close();
   return 0;
}