Cod sursa(job #762263)

Utilizator ion824Ion Ureche ion824 Data 29 iunie 2012 16:14:20
Problema Adapost 2 Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.37 kb
#include<fstream>
#include<iomanip>
#include<cmath>
using namespace std;
int N;
double x[50005],y[50005];

double dist(double x1,double x2,double y1,double y2)
{  double dx=x2-x1,dy=y2-y1;
       return sqrt((dx*dx)+(dy*dy));
}

double verific(double midx,double midy){
       double daux=0;
       for(int i=1;i<=N;++i)       
        daux+=dist(x[i],midx,y[i],midy);              
  return daux;      
}

int main(void){
    ifstream fin("adapost2.in");
    ofstream fout("adapost2.out");
    int i,j,ch;
    double xmax=-1,xmin=1001,ymax=-1,ymin=1001;
    double midx,midy,pasx,pasy;
    fin>>N;
    for(i=1;i<=N;++i)
      {
       fin>>x[i]>>y[i];
       if(x[i]>xmax)xmax=x[i];
       if(x[i]<xmin)xmin=x[i];
       if(y[i]>ymax)ymax=y[i];
       if(y[i]<ymin)ymin=y[i];               
      }
    midx=xmin; midy=ymin; pasx=(xmax-xmin)/2;
    while(pasx>=0.0001){
        ch=0;                      
        if(verific(midx+pasx,midy)<verific(midx,midy)){ midx+=pasx; ch=1; }
        if(verific(midx,midy+pasx)<verific(midx,midy)){ midy+=pasx; ch=1; }
        if(verific(midx-pasx,midy)<verific(midx,midy)){ midx-=pasx; ch=1; }
        if(verific(midx,midy-pasx)<verific(midx,midy)){ midy-=pasx; ch=1; }
        if(!ch)pasx/=2;                          
            }
    fout<<setprecision(4)<<fixed;
    fout<<midx<<' '<<midy<<'\n';
 return 0;   
}