Pagini recente » Cod sursa (job #1874130) | Cod sursa (job #2718783) | Cod sursa (job #2163137) | Cod sursa (job #2347823) | Cod sursa (job #2954683)
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 1e5;
const double INF = 4e9;
struct point {
int x;
int y;
} v[NMAX + 1];
static inline double dist( point a, point b ) {
return sqrt( (long long)( a.x - b.x ) * ( a.x - b.x ) +
(long long)( a.y - b.y ) * ( a.y - b.y ) );
}
static inline int modul( int x ) {
if ( x < 0 ) return -x;
return x;
}
double cmap( int st, int dr ) {
if ( dr - st + 1 <= 3 ) {
double dmin = INF;
for ( int i = st; i <= dr; i ++ ) {
for ( int j = i + 1; j <= dr; j ++ ) {
if ( v[i].y > v[j].y ) {
swap( v[i], v[j] );
}
dmin = min( dmin, dist( v[i], v[j] ) );
}
}
return dmin;
}
int mij = ( st + dr ) / 2;
double dmin = min( cmap( st, mij ), cmap( mij + 1, dr ) );
vector <point> intercls;
vector <point> useful;
int i = st, j = mij + 1;
while ( i <= mij && j <= dr ) {
point aux;
if ( v[i].y < v[j].y ) {
aux = v[i++];
} else {
aux = v[j++];
}
if ( modul( aux.x - v[mij].x ) <= dmin ) {
useful.push_back( aux );
}
intercls.push_back( aux );
}
for ( ; i <= mij; i ++ ) {
if ( modul( v[i].x - v[mij].x ) <= dmin )
useful.push_back( v[i] );
intercls.push_back( v[i] );
}
for ( ; j <= dr; j ++ ) {
if ( modul( v[j].x - v[mij].x ) <= dmin )
useful.push_back( v[j] );
intercls.push_back( v[j] );
}
for ( int i = st; i <= dr; i ++ ) {
v[i] = intercls[i - st];
}
for ( int i = 0; i < useful.size(); i ++ ) {
int till = min( i + 8, (int)useful.size() );
for ( int j = i + 1; j < till; j ++ ) {
dmin = min( dmin, dist( useful[i], useful[j] ) );
}
}
return dmin;
}
int main() {
ifstream fin( "cmap.in" );
ofstream fout( "cmap.out" );
int n;
fin >> n;
for ( int i = 1; i <= n; i ++ ) {
fin >> v[i].x >> v[i].y;
}
sort( v + 1, v + n + 1, []( point a, point b ) {
return a.x < b.x;
});
fout << fixed << setprecision( 7 ) << cmap( 1, n );
return 0;
}