Cod sursa(job #1825384)

Utilizator ovidiu11galeteanu ovidiu ovidiu11 Data 9 decembrie 2016 02:46:34
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 3.77 kb
#include <iostream>
#include <fstream>
#include <math.h>
#include <stdlib.h>
using namespace std;
   int n,x[100000],y[100000],pozitie[100000];
    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(calc2<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.out");
ofstream g("cmap.out");


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

int m;

int ok=1,ok2=1;
m=n;
while(ok2==1)
{ ok2=0;


while(ok==1)
{ok=0;
for(i=1;i<=m/2;i++)
{if(i*2<=m && i*2+1<=m) {if(x[i]>x[2*i] || x[i]>x[2*i+1])
{ ok=1; if(x[2*i]<x[2*i+1]) {aux=x[i]; x[i]=x[2*i]; x[2*i]=aux;
  aux=pozitie[i]; pozitie[i]=pozitie[2*i]; pozitie[2*i]=aux;
  aux=y[i]; y[i]=y[2*i]; y[2*i]=aux;
    }
 else{
        aux=x[i]; x[i]=x[2*i+1]; x[2*i+1]=aux;
 aux=y[i]; y[i]=y[2*i+1]; y[2*i+1]=aux;
 aux=pozitie[i]; pozitie[i]=pozitie[2*i+1]; pozitie[2*i+1]=aux;


 }} }



if(i*2==m && x[i]>x[2*i])
    {ok=1; aux=x[i]; x[i]=x[2*i]; x[2*i]=aux;
            aux=pozitie[i]; pozitie[i]=pozitie[2*i]; pozitie[2*i]=aux;
            aux=y[i]; y[i]=y[2*i]; y[2*i]=aux;

    }}}
if(m>0) {

        m--; ok2=1;  aux=x[1]; x[1]=x[m+1]; x[m+1]=aux; ok=1;
aux=pozitie[1]; pozitie[1]=pozitie[m+1]; pozitie[m+1]=aux;
aux=y[1]; y[1]=y[m+1]; y[m+1]=aux;

}}





  /*  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;
       f.close();
       g.close();}
  //  for(i=0;i<n;i++) {cout<<x[i]<<" "<<y[i]<<endl;}