Pagini recente » Cod sursa (job #2418784) | Cod sursa (job #2940607) | Cod sursa (job #2240528) | Cod sursa (job #1381361) | Cod sursa (job #978950)
Cod sursa(job #978950)
#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<vector>
#define pb push_back
#define maxn 100005
#define inf 1LL<<60
using namespace std;
typedef long long ll;
struct point{int x,y;} px[maxn],py[maxn];
int n,ny;
ll sol;
void read()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d%d",&px[i].x,&px[i].y);
}
int cmpx(point a,point b)
{
if(a.x==b.x) return a.y<b.y;
return a.x<b.x;
}
int cmpy(point a,point b)
{
if(a.y==b.y) return a.x<b.x;
return a.y<b.y;
}
ll dist(point a,point b)
{
return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
ll det_pair(int left,int right)
{
ll pair_min=inf;
if(right-left+1<=3)
{
for(int i=left;i<=right-1;i++)
for(int j=i+1;j<=right;j++)
pair_min=min(pair_min,dist(px[i],px[j]));
return pair_min;
}
int mid=(left+right)/2;
pair_min=min(det_pair(left,mid),det_pair(mid+1,right));
int i=mid,j=mid+1; ny=0;
while(dist(px[mid],px[i])<pair_min && i>=left) py[++ny]=px[i++];
while(dist(px[mid],px[j])<pair_min && j<=right) py[++ny]=px[j++];
sort(py+1,py+ny+1,cmpy);
for(i=1;i<ny;i++)
for(j=i+1;j<=ny;j++)
pair_min=min(pair_min,dist(py[i],py[j]));
return pair_min;
}
void solve()
{
sort(px+1,px+n+1,cmpx);
sol=det_pair(1,n);
printf("%.6lf",sqrt(sol));
}
int main()
{
freopen("cmap.in","r",stdin);
freopen("cmap.out","w",stdout);
read();
solve();
fclose(stdin);
fclose(stdout);
return 0;
}