Pagini recente » Cod sursa (job #88956) | Cod sursa (job #1895311) | Cod sursa (job #156382) | Cod sursa (job #1302696) | Cod sursa (job #978949)
Cod sursa(job #978949)
#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<cstring>
#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],v[maxn];
int n,nv;
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 1LL*(a.x-b.x)*(a.x-b.x)+1LL*(a.y-b.y)*(a.y-b.y);
}
ll det_pair(int left,int right)
{
ll pair_min=inf;
if(right-left<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]));
sort(py+left,py+right+1,cmpy);
return pair_min;
}
int mid=(left+right)/2;
pair_min=min(det_pair(left,mid),det_pair(mid+1,right));
merge(py+left,py+mid+1,py+mid+1,py+right+1,v+1,cmpy);
memcpy(py+left,v+1,right-left+1);
int i,j; nv=0;
for(i=left;i<=right;i++)
if(abs(px[mid].x-px[i].x)<=pair_min)
v[++nv]=px[i];
for(i=1;i<nv;i++)
for(j=i+1;j<=nv && j-i<=7;j++)
pair_min=min(pair_min,dist(v[i],v[j]));
return pair_min;
}
void solve()
{
sort(px+1,px+n+1,cmpx);
for(int i=1;i<=n;i++) py[i]=px[i];
printf("%lf",sqrt(det_pair(1,n)));
}
int main()
{
freopen("cmap.in","r",stdin);
freopen("cmap.out","w",stdout);
read();
solve();
fclose(stdin);
fclose(stdout);
return 0;
}