Cod sursa(job #2969219)

Utilizator andrei_marciucMarciuc Andrei andrei_marciuc Data 22 ianuarie 2023 18:58:33
Problema Cele mai apropiate puncte din plan Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.15 kb
#include <algorithm>
#include <fstream>
#include <iomanip>
#include <cmath>
#include <set>
using namespace std;

ifstream cin( "cmap.in" );
ofstream cout( "cmap.out" );

#define x first
#define y second
set<pair<int, int>> s;

long long dis( pair<int, int> A, pair<int, int> B ) {
	return ( (long long)A.x - B.x ) * ( A.x - B.x ) + ( (long long)A.y - B.y ) * ( A.y - B.y );
}

const int MAX = 1e5 + 3;
pair<int, int> v[ MAX ];
int n;

int main()
{
	cin >> n;
	for( int i = 0; i < n; i++ )
		cin >> v[ i ].x >> v[ i ].y;

	sort( v, v + n, []( pair<int, int> A, pair<int, int> B ) {
			return A.x < B.x;
		} );

	int poz = 0;
	long long pp;
	long long dMin = dis( v[ 0 ], v[ 1 ] );
	for( int i = 0; i < n; i++ ) {
		while( poz < i && ((long long)v[ i ].x - v[ poz ].x) * (v[ i ].x - v[ poz ].x) > dMin )
			s.erase( v[ poz++ ] );

		for( auto it = s.lower_bound( { v[ i ].y - dMin, 0 } ); it != s.end() && (*it).y <= v[ i ].y + dMin; it++ ) {
			if( ( pp = dis( v[ i ], (*it) ) ) < dMin )
				dMin = pp;
		}
		s.insert( v[ i ] );
	}

	cout << fixed << setprecision( 6 );
	cout << (double)sqrt( dMin ) << '\n';
    return 0;
}