Pagini recente » Cod sursa (job #705162) | Cod sursa (job #95625) | Cod sursa (job #2608524) | Cod sursa (job #2414320) | Cod sursa (job #978932)
Cod sursa(job #978932)
#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];
int n;
ll sol;
vector <point> py;
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=1;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(pair_min,det_pair(left,mid));
pair_min=min(pair_min,det_pair(mid+1,right));
int i=mid,j=mid+1;
while(dist(px[mid],px[i])<pair_min && i>=left) py.pb(px[i--]);
while(dist(px[mid],px[j])<pair_min && j<=right) py.pb(px[j++]);
sort(py.begin(),py.end(),cmpy);
for(unsigned int i=0;i<py.size()-1;i++)
for(unsigned int j=i+1;j<py.size() && j-i<=7;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;
}