Pagini recente » Cod sursa (job #1397980) | Cod sursa (job #2754468) | Cod sursa (job #1824743) | Cod sursa (job #2332989) | Cod sursa (job #2466879)
#include <fstream>
#include <cmath>
#include <iomanip>
#include <algorithm>
using namespace std;
ifstream fin ("cmap.in");
ofstream fout ("cmap.out");
const int MAXN = 1e5 + 5;
struct Point{
int x,y;
bool operator < ( const Point& ob) const {
return x < ob.x;
};
};
Point p[MAXN],v[MAXN];
int n;
double dist( Point x,Point y) {
return sqrt((x.x-y.x) * (x.x-y.x) + (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 = 10000000000;
if ( dr - st <= 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) >>1;
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];
ind = 0;
for ( int i = st; i <= dr; ++i)
if ( fabs(p[i].x - xmij) < ans)
v[++ind] = p[i];
for ( int 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);
}