Cod sursa(job #1825380)

Utilizator ovidiu11galeteanu ovidiu ovidiu11 Data 9 decembrie 2016 02:33:30
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.84 kb
#include <iostream>
#include <fstream>
#include <math.h>
#include <stdlib.h>
using namespace std;
   int n,x[100],y[100],pozitie[100];
    double minim,xc1,yc1,xc2,yc2;



void divide(int li,int ls,double&minim,double&xc1,double&yc1)
{if(ls-li<3)

{ if((ls-li)==1)
    {long calc;
    calc=sqrt(  (   x[pozitie[li]]-x[pozitie[ls]]  )    *(  x[pozitie[li]]-x[pozitie[ls]]  )+
                (   y[pozitie[li]]-y[pozitie[ls]]  )    *(  y[pozitie[li]]-y[pozitie[ls]]  )    ) ;
if(calc<minim) {minim=calc; xc1=pozitie[li];  yc1=pozitie[ls]; }


}
else{   double calc;
       double calc1;
        double calc2;

    calc=sqrt(  (   x[pozitie[li]]-x[pozitie[ls]]  )    *(  x[pozitie[li]]-x[pozitie[ls]]  )+
                (   y[pozitie[li]]-y[pozitie[ls]]  )    *(  y[pozitie[li]]-y[pozitie[ls]]  )    ) ;
                if(calc<minim) {minim=calc; xc1=pozitie[li]; yc1=pozitie[ls]; }
    calc1=sqrt(  (   x[pozitie[li+1]]-x[pozitie[ls]]  )    *(  x[pozitie[li+1]]-x[pozitie[ls]]  )+
                (   y[pozitie[li+1]]-y[pozitie[ls]]  )    *(  y[pozitie[li+1]]-y[pozitie[ls]]  )    ) ;
                if(calc1<minim) {minim=calc; xc1=pozitie[li+1];  yc1=pozitie[ls]; }
    calc2=sqrt(  (   x[pozitie[li]]-x[pozitie[ls-1]]  )    *(  x[pozitie[li]]-x[pozitie[ls-1]]  )+
                (   y[pozitie[li]]-y[pozitie[ls-1]]  )    *(  y[pozitie[li]]-y[pozitie[ls-1]]  )    ) ;
                if(calc<minim) {minim=calc; xc1=pozitie[li];  yc1=pozitie[li-1]; }







}}
else{
        int mijloc;
mijloc=(ls+li)/2;






double xx[8],yy[8],pozz[8];
int k=0; int i;
for(i=0;i<n;i++){if(abs(x[i]-x[mijloc])<minim && abs(y[i]-y[mijloc])<minim) {xx[k]=x[i];yy[k]=y[i]; pozz[k]=pozitie[i]; k++; }
}

k--;
for(i=0;i<=k;i++)
{for(int j=i+1;j<=k;j++)
{
   double calc;
    calc=sqrt( (xx[i]-xx[j])*(xx[i]-xx[j]) + (yy[i]-yy[j])*(yy[i]-yy[j]) );
    if(calc<minim) {  xc1=pozz[i]; yc1= pozz[j];  minim=calc;}                                                               }



      }


divide(li,mijloc,minim,xc1,yc1);
divide(mijloc,ls,minim,xc1,yc1);


}



}




int main()
{ifstream f("cmap.in");
ofstream g("cmap.out");


   f>>n;
int i,j,aux;
   for(i=0;i<n;i++)
    {f>>x[i]>>y[i]; pozitie[i]=i;
}


    for(i=0;i<n;i++)
    {
        for(j=i+1;j<n;j++)
        {
            if(x[i]>x[j]){
                    aux=x[i];
                    x[i]=x[j];
                    x[j]=aux;
                    aux=y[i];
                    y[i]=y[j];
                    y[j]=aux;
                    aux=pozitie[i];
                    pozitie[i]=pozitie[j];
                    pozitie[j]=aux;

        }

        }
    }
    minim=sqrt((x[5]-x[1])*(x[5]-x[1])+ (y[5]-y[1])*(y[5]-y[1])  );

divide(0,n-1,minim,xc1,yc1);

       g<<minim;
  //  for(i=0;i<n;i++) {cout<<x[i]<<" "<<y[i]<<endl;}


}