Cod sursa(job #203341)

Utilizator AndreiDDiaconeasa Andrei AndreiD Data 15 august 2008 16:46:36
Problema Adapost 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.5 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=FALSE;
      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=TRUE;
           }   
         }   
      if (ok==FALSE)
      pas/=2;   
       }   
printf("%.4lf %.4lf", pmin1,pmin2);   
return 0;   
}