Pagini recente » Cod sursa (job #617714) | Cod sursa (job #2923583) | Cod sursa (job #1673084) | Cod sursa (job #1016058) | Cod sursa (job #1360875)
#include <iostream>
#include <iomanip>
#include <fstream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
ifstream F("cmap.in");
ofstream G("cmap.out");
const int N = 100010;
int n;
pair<int,int> a[N];
double dist(pair<int,int> a,pair<int,int> b)
{
return sqrt( 1LL*(a.first-b.first)*(a.first-b.first) + 1LL*(a.second-b.second)*(a.second-b.second) );
}
bool cmp(pair<int,int> a,pair<int,int> b)
{
return a.second < b.second || ( a.second == b.second && a.first <= b.first );
}
double solve(int l,int r)
{
if ( l == r ) return 1<<30;
if ( r == l+1 ) return dist(a[l],a[r]);
int m = (l + r) / 2;
double ans = min( solve(l,m),solve(m+1,r) );
int x = a[m].first;
vector< pair<int,int> > pt;
for (int i=l;i<=r;++i)
if ( max(a[i].first-a[m].first,a[m].first-a[i].first) <= ans )
pt.push_back( a[i] );
sort(pt.begin(),pt.end(),cmp);
for (int i=0;i<int(pt.size());++i)
for (int j=1;j<=7;++j)
if ( i+j < int(pt.size()) )
ans = min(ans,dist(pt[i],pt[i+j]));
return ans;
}
int main()
{
F>>n;
for (int i=1;i<=n;++i)
F>>a[i].first>>a[i].second;
sort(a+1,a+n+1);
G<<fixed<<setprecision(6)<<solve(1,n)<<'\n';
}