Pagini recente » Cod sursa (job #3239393) | Cod sursa (job #264470) | Cod sursa (job #2927537) | Cod sursa (job #1235029) | Cod sursa (job #1713605)
#include<cstdio>
#include<algorithm>
#include<cmath>
#define MAXN 100010
#define INF (1LL<<61)
using namespace std;
pair<long long,long long> v[MAXN],temp[MAXN];
long long Distance(pair<long long,long long> a,pair<long long,long long> b){
return (long long)(a.first-b.first)*(a.first-b.first)+(long long)(a.second-b.second)*(a.second-b.second);
}
long long minimum(long long a,long long b){
if(a<b)
return a;
return b;
}
long long Divide(int left,int right){
int middle=(left+right)/2,i,j,k,current=0,middleX;
middleX=v[middle].first;
long long answer;
if(left>=right)
return INF;
if(left+1==right){
if(v[left].second>v[right].second||(v[left].second==v[right].second&&v[left].first>v[right].first))
swap(v[left],v[right]);
return Distance(v[left],v[right]);
}
answer=minimum(Divide(left,middle),Divide(middle+1,right));
i=left;
j=middle+1;
k=0;
while(i<=middle&&j<=right)
if(v[i].second>v[j].second||(v[i].second==v[j].second&&v[i].first>v[j].first)){
k++;
temp[k]=v[j];
j++;
}
else{
k++;
temp[k]=v[i];
i++;
}
while(i<=middle){
k++;
temp[k]=v[i];
i++;
}
while(j<=right){
k++;
temp[k]=v[j];
j++;
}
for(i=left;i<=right;i++)
v[i]=temp[i-left+1];
for(i=left;i<=right;i++)
if((long long)(v[i].first-middleX)*(v[i].first-middleX)<=answer){
current++;
temp[current]=v[i];
}
for(i=1;i<current;i++)
for(j=i+1;j<=current&&(long long)(temp[j].second-temp[i].second)*(temp[j].second-temp[i].second)<=answer;j++)
answer=minimum(answer,Distance(temp[i],temp[j]));
return answer;
}
int main(){
freopen("cmap.in","r",stdin);
freopen("cmap.out","w",stdout);
int n,i;
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%lld%lld",&v[i].first,&v[i].second);
sort(v+1,v+n+1);
printf("%f",sqrt(Divide(1,n)));
return 0;
}