Pagini recente » Cod sursa (job #2779163) | Cod sursa (job #1479530) | Cod sursa (job #2910455) | Cod sursa (job #1599111) | Cod sursa (job #2871152)
#include <fstream>
#include <vector>
#include <deque>
#include <algorithm>
#include <climits>
#include <iomanip>
#include <cmath>
#define MOD 666013
#define INT_MAX 1000000000
using namespace std ;
ifstream cin ("cmap.in") ;
ofstream cout ("cmap.out") ;
struct pct
{
long double x, y ;
};
long double d(pct a, pct b)
{
return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y)) ;
}
pct v[120009] ;
long double merg(int st, int dr)
{
if(dr - st == 1)
return d(v[st], v[dr]) ;
if(st == dr)
return (long double)INT_MAX * 3 ;
int mid = (st + dr) / 2 ;
long double mn = min(merg(st, mid), merg(mid + 1, dr)) ;
/// consideram doar punctele care pe axa x
long double l = (v[mid + 1].x + v[mid].x) / 2 ;
vector<pct> X, Y ;
for(int f = st ; f <= mid ; f ++)
if(l - v[f].x + v[mid + 1].x - l < mn)X.push_back(v[f]) ;
for(int f = mid + 1 ; f <= dr ; f ++)
if(v[f].x - l + l - v[mid].x < mn)Y.push_back(v[f]) ;
///sort(X.begin(), X.end(), ord2) ; /// sorteaza dupa y
///sort(Y.begin(), Y.end(), ord2) ;
for(int f = 0 ; f < X.size() ; f ++)
for(int e = 0 ; e < Y.size() ; e ++)
mn = min(mn, d(X[f], Y[e])) ;
return mn ;
}
bool ord(pct a, pct b)
{
return a.x < b.x ;
}
int main()
{
int n ;
cin >> n ;
for(int f = 1 ; f <= n ; f ++)
cin >> v[f].x >> v[f].y ;
sort(v + 1, v + n + 1, ord) ;
cout << fixed << setprecision(6) << merg(1, n) ;
return 0 ;
}
/// 1990