Cod sursa(job #130480)

Utilizator RobytzzaIonescu Robert Marius Robytzza Data 1 februarie 2008 12:21:54
Problema Adapost 2 Scor 23
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.32 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,double kkt)
{
   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+kkt,y,a[j],b[j]);
		 S3+=dist (x,y-kkt,a[j],b[j]);
		 S4+=dist (x-kkt,y,a[j],b[j]);}
	 if (S1<Smin ){
		 Smin=S1;
		 ok=1;
			 y+=kkt;
	 }

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

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

	 if (S4<Smin )
	 {
	 Smin=S4;
	 x-=kkt;
	 ok=1;
	 }
	 f(ok,kkt);
}

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,100);
	f(1,10);
	f(1,1);
	f(1,0.1);
	f(1,0.01);
	f(1,0.001);
	f(1,0.0001);
	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;
}