Pagini recente » Cod sursa (job #2377116) | Cod sursa (job #2553202) | Cod sursa (job #554819) | Cod sursa (job #2466049) | Cod sursa (job #3188592)
#include<bits/stdc++.h>
using namespace std;
ifstream F("cmap.in");
ofstream G("cmap.out");
#define P pair<int,int>
P a[100000];
int i,n;
bool A(P a,P b)
{
return a.first<b.first||(a.first==b.first&&a.second<b.second);
}
bool B(P a,P b)
{
return a.second<b.second||(a.second==b.second&&a.first<b.first);
}
double C(P a,P b)
{
return sqrt(1LL*(a.first-b.first)*(a.first-b.first)+1LL*(a.second-b.second)*(a.second-b.second));
}
double E(P a[],int n)
{
if(n<4) {
int i,j;
double s=1e19,t;
for(i=0;i<n-1;++i)
for(j=i+1;j<n;++j)
if(t=C(a[i],a[j]),t<s)
s=t;
return s;
}
int m=n/2,i,j,k;
double d=min(E(a,m),E(a+m,n-m)),e;
P b=a[m],r[n];
for(k=i=0;i<n;++i)
if(abs(a[i].first-b.first)<d)
r[k++]=a[i];
for(sort(r,r+k,B),i=0;i<k-1;++i)
for(j=i+1;j<k&&r[j].second-r[i].second<d;++j)
if(e=C(r[i],r[j]),e<d)
d=e;
return d;
}
int main()
{
for(F>>n;i<n;F>>a[i].first>>a[i].second,++i);
return sort(a,a+n,A),G<<fixed<<setprecision(6)<<E(a,n),0;
}