Pagini recente » Cod sursa (job #1835879) | Cod sursa (job #785537) | Cod sursa (job #1400730) | Cod sursa (job #453265) | Cod sursa (job #2100518)
#include <iostream>
#include<fstream>
#include<stdlib.h>
#include<cmath>
#include<algorithm>
#include<iomanip>
#define INF 1000000000000000000000
using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");
struct punct
{
int x;
int y;
};
punct *vect,*X,*Y;
int nr;
void afisare(punct *vect,int inc, int dim)
{
for(int i=inc; i<=dim; i++)
cout<<vect[i].x<<" "<<vect[i].y<<endl;
cout<<endl;
}
int compare_abs(const void* a, const void* b)
{
punct* A=(punct*)a;
punct* B=(punct*)b;
if(A->x<B->x) return -1;
if(A->x==B->x) return 0;
if(A->x>B->x) return 1;
}
int compare_ord(const void* a, const void* b)
{
punct* A=(punct*)a;
punct* B=(punct*)b;
if(A->y<B->y) return -1;
if(A->y==B->y) return 0;
if(A->y>B->y) return 1;
}
double distanta(punct a, punct b)
{
double z;
z=sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
return z;
}
double DivImp( int st, int dr,punct *Y)
{
if(st==dr) return INF;
if(dr-st+1==2)
{
double z=distanta(X[st],X[dr]);
return z;
}
if(dr-st+1==3)
{
double aux1,aux2,aux3;
aux1=distanta(X[st],X[st+1]);
aux2=distanta(X[st+1],X[dr]);
aux3=distanta(X[st],X[dr]);
double minim;
if(aux1<aux2) minim=aux1;
else minim=aux2;
if(aux3<minim) minim=aux3 ;
return minim;
}
int mij=(st+dr)/2;
int n=dr-st+1;
punct *SY,*DY,*LY;
SY=new punct[nr+1];
DY=new punct[nr+1];
LY=new punct[nr+1];
int dim1,dim2,dim3;
dim1=dim2=dim3=-1;
for(int i=0; i<n; i++)
if(Y[i].x<=X[mij].x)
{
dim1++;
SY[dim1]=Y[i];
}
else
{
dim2++;
DY[dim2]=Y[i];
}
double d1=DivImp(st,mij,SY);
double d2=DivImp(mij+1,dr,DY);
double d=min(d1,d2);
for(int i=0; i<n; i++)
if((abs(Y[i].x-X[mij].x)<=d)&& (Y[i].y-X[mij].y)<=d)
{
dim3++;
LY[dim3]=Y[i];
}
double d3=distanta(LY[0],LY[1]);
double dist_aux=0;
for(int i=0; i<dim3; i++)
for(int j=i+1; j<=dim3; j++)
{
dist_aux=distanta(LY[i],LY[j]);
if(dist_aux<d3) d3=dist_aux;
}
d=min(d,d3);
delete[]SY;
delete[]DY;
delete[]LY;
return d;
}
int main()
{
f>>nr;
vect=new punct[nr+1];
X=new punct[nr+1];
Y=new punct[nr+1];
for(int i=0; i<nr; i++)
{
f>>vect[i].x>>vect[i].y;
X[i]=vect[i];///vectorul in care o sa le am sortate dupa abscisa
Y[i]=vect[i];///vectorul in care o sa le am sortate dupa ordonata
}
qsort(X,nr,sizeof(punct),compare_abs);///ordonez vectorul X dupa abscisa
qsort(Y,nr,sizeof(punct),compare_ord);///ordonez vectorul Y dupa ordonata
g<<fixed<<setprecision(6)<<DivImp(0,nr-1,Y);
delete[] vect;
delete[] X;
delete[] Y;
f.close();
g.close();
return 0;
}