Cod sursa(job #3297481)

Utilizator Arhiva_EducationalaArhiva Educationala Arhiva_Educationala Data 22 mai 2025 18:02:29
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.89 kb
#include <bits/stdc++.h>

using namespace std;

const int NMAX = 1e5;

using Point = complex<double>;

Point v[NMAX + 1];

mt19937 rng( 0 );

int main() {
    ifstream fin( "cmap.in" );
    ofstream fout( "cmap.out" );
    int n;

    fin >> n;
    Point rot = polar( (double)1, (double)(rng() % 1000) );
    for ( int i = 1, x, y; i <= n; i ++ ) {
        fin >> x >> y;
        v[i] = Point{(double)x, (double)y};
        v[i] *= rot;
    }


    double minDist = abs( v[2] - v[1] );

    sort( v + 1, v + n + 1, []( Point a, Point b ) {
        return a.real() < b.real();
    });
    for ( int i = 2; i <= n; i ++ ) {
        int j = i - 1;
        while ( j > 0 && v[i].real() - v[j].real() < minDist ) {
            minDist = min( minDist, abs( v[i] - v[j] ) );
            j --;
        }
    }
    fout << fixed << setprecision( 6 ) << minDist << '\n';
    return 0;
}