Pagini recente » Cod sursa (job #1801843) | Cod sursa (job #2886476) | Cod sursa (job #2750897) | Cod sursa (job #1890179) | Cod sursa (job #2466914)
#include <fstream>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <algorithm>
using namespace std;
ifstream fin ("cmap.in");
ofstream fout ("cmap.out");
const int MAXN = 1e5 + 5;
#define x first
#define y second
using Point = pair < int ,int > ;
pair < int ,int > p[MAXN],v[MAXN];
int n;
double dist( Point x,Point y) {
return sqrt((double)(x.x-y.x) * (x.x-y.x) + (double)(x.y-y.y) * (x.y-y.y));
}
bool cmp(Point x, Point y) {
return (x.y < y.y);
}
double solve(int st, int dr) {
double ans = INFINITY;
if ( dr - st + 1 <= 3) {
sort(p+st+1,p+dr+1,cmp);
for ( int i = st; i <= dr; ++i)
for ( int j = i + 1; j <= dr; ++j)
ans = min(ans,dist(p[i],p[j]));
return ans;
}
int mj;
mj = ( st + dr) / 2 ;
int xmij = p[mj].x;
ans = min(solve(st,mj),solve(mj+1,dr));
int i = st, j = mj +1,ind = 0;
while ( i <= mj and j <= dr) {
if ( p[i].y < p[j].y)
v[++ind] = p[i++];
else
v[++ind] = p[j++];
}
for ( ; i <= mj ; ++i) v[++ind] = p[i];
for ( ; j <= dr ; ++j) v[++ind] = p[j];
for ( int i = st; i <= dr; ++i)
p[i] = v[i-st+1];
ind = 0;
for ( i = st; i <= dr; ++i)
if ( fabs(p[i].x - xmij) <= ans)
v[++ind] = p[i];
for ( i = 1; i <= ind; ++i)
for( int j = i + 1; j <= min(i + 7,ind); ++j)
ans = min(ans,dist(v[i],v[j]));
return ans;
}
int main() {
fin >> n;
for ( int i = 1; i <= n; ++i)
fin >> p[i].x >> p[i].y;
sort(p+1,p+1+n);
fout << setprecision(8) << fixed;
fout << solve(1,n);
}