Cod sursa(job #253270)

Utilizator 630r63Ilinca George Mihai 630r63 Data 5 februarie 2009 16:51:38
Problema Adapost 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
 #include <fstream.h>  
 #include <math.h>  
   
 double x,y,a[50005],b[50005];  
 double Smin;  
 long n;  
 const double l[10]={-1,-1,-1,0,0,1,1,1};  
 const double c[10]={-1,0,1,-1,1,-1,0,1};  
   
 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=1000;  
 while (d>=0.00005)  
 {  
    int ok=1;  
    while (ok){  
    ok=0;  
    double x1=x,y1=y,S=0;  
    for (int k=0;k<8;k++)  
    {  
        S=0;  
        for (int i=0;i<n;i++)  
        S+= dist(x1+(double)l[k]*d,y1+(double)c[k]*d,a[i],b[i]);  
        if (S<Smin)  
        {  
       Smin=S;  
       x=x1+(double)l[k]*d;  
       y=y1+(double)c[k]*d;  
       ok=1;  
        }  
      }  
    }  
    d/=2;  
   }  
 }  
   
 int main ()  
 {  
    citire();  
    Smin=1000000000;  
    for (int i=0;i<n;i++)  
    {  
        x+=a[i];  
        y+=b[i];  
    }  
    x/=n;  
    y/=n;  
    f();  
    fout<<x<<" "<<y<<"\n";  
    fout.close();  
    fin.close();  
    return 0;  
}