Cod sursa(job #203340)

Utilizator AndreiDDiaconeasa Andrei AndreiD Data 15 august 2008 16:41:08
Problema Adapost 2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <stdio.h>
#include <math.h>
#include <string.h>

#define FIN "adapost2.in"
#define FOUT "adapost2.out"
#define NMAX 51000
#define TRUE 1
#define FALSE 0
#define sqr(a,b) (a-b)*(a-b)

int n,i,j,k;
double pas;
double p1,p2;
double r1,r2;
double pmin1,pmin2;
double dist,dist_min;
int ok;
int di[4]={0,0,1,-1};
int dj[4]={1,-1,0,0};

double v1[NMAX];
double v2[NMAX];


double distanta(double a, double b, double c, double d)
{
return sqrt(sqr(a,c)+sqr(b,d));
}


int main()
{
freopen(FIN,"rt",stdin);
freopen(FOUT,"wt",stdout);

scanf("%d", &n);

for (i=1;i<=n;++i)
    {
    scanf("%lf %lf", &v1[i], &v2[i]);
    r1+=v1[i];
    r2+=v2[i];
    }
r1/=n;
r2/=n;
pmin1=r1;
pmin2=r2;
dist_min=0;
for (i=1;i<=n;++i)
    dist_min+=distanta(v1[i],v2[i],r1,r2);
    pas=100.0;
while (pas>0.0005)
      {
      ok=0;
      for (k=0;k<4;++k)
	   {
	    p1=r1+di[k]*pas;
	    p2=r2+dj[k]*pas;
	    dist=0;
	    for (i=1;i<=n;++i)
		dist+=distanta(v1[i],v2[i],p1,p2);
	    if (dist>dist_min)
	       {
	       dist_min=dist;
	       pmin1=p1;
	       pmin2=p2;
	       r1=p1;
	       r2=p2;
	       ok=1;
	       }
	     }
      if (ok==1)
	  pas/=2;
       }
printf("%.4lf %.4lf", pmin1,pmin2);
return 0;
}