Pagini recente » Cod sursa (job #1692777) | Cod sursa (job #688977) | Cod sursa (job #2852071) | Cod sursa (job #415777) | Cod sursa (job #3188589)
#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 D(P s[],int n,double d)
{
double p;
int i,j;
for(sort(s,s+n,B),i=0;i<n-1;++i)
for(j=i+1;j<n&&s[j].second-s[i].second<d;++j)
if(p=C(s[i],s[j]),p<d)
d=p;
return d;
}
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;
double d=min(E(a,m),E(a+m,n-m));
P b=a[m],r[n];
for(j=i=0;i<n;++i)
if(abs(a[i].first-b.first)<d)
r[j++]=a[i];
return min(d,D(r,j,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;
}