Pagini recente » Cod sursa (job #1368630) | Cod sursa (job #1893111) | Cod sursa (job #2571541) | Cod sursa (job #2256404) | Cod sursa (job #1825381)
#include <iostream>
#include <fstream>
#include <math.h>
#include <stdlib.h>
using namespace std;
int n,x[10000],y[10000],pozitie[10000];
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;}
}