Pagini recente » Cod sursa (job #2222945) | Cod sursa (job #1145503) | Cod sursa (job #1251192) | Cod sursa (job #1446468) | Cod sursa (job #1427129)
#include <iostream>
#include<fstream>
#include<algorithm>
#include <math.h>
#define Nmax 100001
#define oo 1000000000000000
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
int n,Lenght,nr=0;
struct point
{
long long int x,y;
};
point v[Nmax],Y[Nmax], sir[Nmax],aux[Nmax];
long long distance(point p1, point p2)
{
return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}
bool cmp1(point p1, point p2)
{
return p1.x<p2.x;
}
void Swap(point p1, point p2)
{
swap(p1.x,p2.x);
swap(p1.y,p2.y);
}
void Interclasare(long long int st,long long int m,long long int dr)
{
long long int i,j;
i=st;
j=m+1;
while(i<=m&&j<=dr)
if(Y[i].y<Y[j].y) aux[++nr]=Y[i++];
else aux[++nr]=Y[j++];
while(i<=m) aux[++nr]=Y[i++];
while(j<=dr) aux[++nr]=Y[j++];
for(i=st;i<=dr;i++) Y[i]=aux[i];
}
long long DivideImpera(int st,int dr)
{
int i,j;
if(st>=dr)
return oo;
long long DMIN=oo;
if(dr-st<=2)
{
for(i=st;i<=dr;i++)
Y[i]=v[i];
for(i=st;i<dr;i++)
for(j=i+1;j<=dr;j++)
if(Y[i].y>Y[i].y) Swap(Y[i],Y[j]);
for(i=st;i<dr;i++)
for(j=i+1;j<=dr;j++)
DMIN=min(distance(v[i],v[j]),DMIN);
return DMIN;
}
int m=(st+dr)/2;
int mij=v[m].x;
long long d1=DivideImpera(st,m);
long long d2=DivideImpera(m+1,dr);
DMIN=min(d1,d2);
Interclasare(st,m,dr);
for(i=st;i<=dr;i++)
if(abs(Y[i].x-Y[m].x)<=DMIN) sir[++Lenght]=Y[i];
for(i=1;i<=Lenght;i++)
for(j=1;j<=7 && i+j<=Lenght;j++)
DMIN=min(distance(sir[i],sir[i+j]),DMIN)
return DMIN;
}
int main()
{
fin>>n;
int i;
for(i=1;i<=n;i++)
fin>>v[i].x>>v[i].y;
sort(v+1,v+n+1,cmp1);
DMIN=DivideImpera(1,n);
fout<<fixed<<setprecision(6)<<DMIN;
return 0;
}