Cod sursa(job #130464)

Utilizator RobytzzaIonescu Robert Marius Robytzza Data 1 februarie 2008 11:43:11
Problema Adapost 2 Scor 59
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.91 kb
#include <stdio.h>
#include <math.h>
double a[50005],b[50005];
int n;
double Smin=1000000,x=0,y=0;
void citire()
{
	freopen ("adapost2.in","r",stdin);
	scanf ("%d",&n);
	for ( int i=0 ;i <n ;i++ )
		scanf ("%lf%lf",&a[i],&b[i]);
	fclose(stdin);
}

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

void f (int ok)
{
   if (ok==0)
      return ;
      ok=0;
   double S1=0,S2=0,S3=0,S4=0;
   int j;

     for (j=0;j<n;j++){
	  S1+=dist(x,y+0.1,a[j],b[j]);
		 S2+=dist (x+0.1,y,a[j],b[j]);
		 S3+=dist (x,y-0.1,a[j],b[j]);
		 S4+=dist (x-0.1,y,a[j],b[j]);}
	 if (S1<Smin ){
		 Smin=S1;
		 ok=1;
			 y+=0.1;
	 }

	 if (S2<Smin ){
		 Smin=S2;
		 ok=1;
		 x+=0.1;
	 }

	 if (S3<Smin ){
	 Smin=S3;
	 y-=0.1;
	 ok=1;}

	 if (S4<Smin )
	 {
	 Smin=S4;
	 x-=0.1;
	 ok=1;
	 }
	 f(ok);
}
void g (int ok)
{
     if (ok==0)
	 return ;
	 ok=0;
     double S1=0,S2=0,S3=0,S4=0;
     int j;
     for (j=0;j<n;j++){
	  S1+=dist(x,y+0.01,a[j],b[j]);
		 S2+=dist (x+0.01,y,a[j],b[j]);
		 S3+=dist (x,y-0.01,a[j],b[j]);
		 S4+=dist (x-0.01,y,a[j],b[j]);}
	 if (S1<Smin ){
	 ok=1;
		 Smin=S1;
			 y+=0.01;		       }
	 if (S2<Smin ){
		 Smin=S2;
		 ok=1;
		 x+=0.01;		 }
	 if (S3<Smin ){
		 ok=1;
		 y-=0.01;
		 Smin=S3;                       }
	 if (S4<Smin ){
		 ok=1;
		 Smin=S4;
		 x-=0.01;		       }
	 g(ok);
}

void d (int ok)
{
     if (ok==0)
	return ;
     ok=0;
	double S1=0,S2=0,S3=0,S4=0;
	int j;
     for (j=0;j<n;j++){
	  S1+=dist(x,y+0.001,a[j],b[j]);
		 S2+=dist (x+0.001,y,a[j],b[j]);
		 S3+=dist (x,y-0.001,a[j],b[j]);
		 S4+=dist (x-0.001,y,a[j],b[j]);}
	 if (S1<Smin ){
		  ok=1;
			 y+=0.001;
		 Smin=S1;                       }
	 if (S2<Smin ){
		ok=1;
		 Smin=S2;
		 x+=0.001;		       }
	 if (S3<Smin ){
		 ok=1;
		 y-=0.001;
		 Smin=S3;                       }
	 if (S4<Smin ){
		 ok=1;
		 Smin=S4;
		 x-=0.001;		    }
	 d(ok);
}
void tt (int ok)
{

if (ok==0)
   return ;
   ok=0;
	double S1=0,S2=0,S3=0,S4=0;
       int j;
     for (j=0;j<n;j++){
	  S1+=dist(x,y+0.0001,a[j],b[j]);
		 S2+=dist (x+0.0001,y,a[j],b[j]);
		 S3+=dist (x,y-0.0001,a[j],b[j]);
		 S4+=dist (x-0.0001,y,a[j],b[j]);}
	 if (S1<Smin ){
		 ok=1;
			 y+=0.0001;
		 Smin=S1;                       }
	 if (S2<Smin ){
		 ok=1;
		 Smin=S2;
		 x+=0.0001;		    }
	 if (S3<Smin ){
		 ok=1;
		 y-=0.0001;
		 Smin=S3;                       }
	 if (S4<Smin ){
		 ok=1;
		 Smin=S4;
		 x-=0.0001;		   }
	 tt(ok);
}

int main ()
{
	citire();
	Smin=0;
	for (int k=0;k<n;k++)
	{
	    x+=a[k];
	    y+=b[k];
	}
	x/=n;
	y/=n;
	for (int i=0; i<n ;i++)
		 Smin+=dist (x,y,a[i],b[i]);
	f(1);
	g(1);
	d(1);
	tt(1);
	long  x1=x*10000;
	long y1=y*10000;
	freopen ("adapost2.out","w",stdout);
	printf ("%ld.%ld ",x1/10000,x1%10000);
	printf ("%ld.%ld\n",y1/10000,y1%10000);
	fclose(stdout);
	return 0;
}