Pagini recente » Borderou de evaluare (job #804515) | Cod sursa (job #1198437) | Cod sursa (job #264810) | Cod sursa (job #2756154) | Cod sursa (job #2100349)
#include <iostream>
#include<fstream>
#include<stdlib.h>
#include<cmath>
#include<algorithm>
#include<iomanip>
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 dim)
{
for(int i=0;i<nr;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(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],X[dr]);
aux3=distanta(X[st+1],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=st;i<=dr;i++)
if(abs(Y[i].x-X[mij].x)<=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=max(1,i-7);j<i;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 vectoeul Y dupa ordonata
g<<fixed<<setprecision(6)<<DivImp(0,nr-1,Y);
delete[] vect;
delete[] X;
delete[] Y;
f.close();
g.close();
return 0;
}