Pagini recente » Cod sursa (job #317773) | Cod sursa (job #3161965) | info-arena 2.0 | Cod sursa (job #545496) | Cod sursa (job #2971970)
#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <set>
#define NMAXX 100000
#define INF -1000000000
using namespace std;
struct elem {
int x, y;
};
int n;
elem v[NMAXX];
bool cmpx( elem a, elem b ) {
return a.x < b.x;
}
bool cmpy( elem a, elem b ) {
return a.y < b.y;
}
set<elem, decltype(cmpy)*> active(cmpy);
double dist( const elem& a, const elem& b ) {
return sqrt(((long long)a.x - b.x) * (a.x - b.x) + ((long long)a.y - b.y) * (a.y - b.y));
}
int main() {
FILE *fin, *fout;
int i, j;
double minn;
fin = fopen( "cmap.in", "r" );
fout = fopen( "cmap.out", "w" );
fscanf( fin, "%d", &n );
for ( i = 0; i < n; i++ )
fscanf( fin, "%d%d", &v[i].x, &v[i].y );
sort( v, v + n, cmpx );
minn = 1e9;
active.insert( v[0] );
j = 0;
for ( i = 1; i < n; i++ ) {
while ( v[i].x - v[j].x > minn )
active.erase( v[j++] );
auto it = active.lower_bound({ INF, v[i].y - minn });
while ( it != active.end() && abs( it -> y - v[i].y ) <= minn ) {
minn = min( minn, dist( *it, v[i] ) );
it++;
}
active.insert( v[i] );
}
fprintf( fout, "%lf", minn );
fclose( fin );
fclose( fout );
return 0;
}