Pagini recente » Cod sursa (job #403289) | Cod sursa (job #2740923) | Cod sursa (job #448915) | Cod sursa (job #1344827) | Cod sursa (job #2972484)
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 1e5;
ifstream fin( "cmap.in" );
ofstream fout( "cmap.out" );
struct Point{
int x;
int y;
};
Point points[NMAX+1];
double dist( Point a, Point b ) {
return sqrt( 1LL * abs( a.x - b.x ) * abs( a.x - b.x ) + 1LL * abs( a.y - b.y ) * abs( a.y - b.y ) );
}
bool cmp( Point a, Point b ) {
return ( a.x < b.x ) || ( a.x == b.x && a.y < b.y );
}
inline bool operator <( const Point& a, const Point& b ) {
return ( a.y < b.y ) || ( a.y == b.y && a.x < b.x );
}
set<Point> activePoints;
int main() {
int n, i, j;
double minDist;
fin >> n;
for( i = 0; i < n; i++ ) {
fin >> points[i].x >> points[i].y;
}
sort( points, points + n, cmp );
activePoints.insert( points[0] );
j = 0;
minDist = DBL_MAX;
for( i = 1; i < n; i++ ) {
while( j < i && points[i].x - points[j].x > minDist ) {
activePoints.erase( points[j] );
j++;
}
auto it = activePoints.lower_bound( { INT_MIN, points[i].y - minDist } );
while( it != activePoints.end() && abs( (*it).y - points[i].y ) <= minDist ) {
minDist = min( minDist, dist( *it, points[i] ) );
it++;
}
activePoints.insert( points[i] );
}
fout << fixed << setprecision( 6 );
fout << minDist;
return 0;
}