Cod sursa(job #2971970)

Utilizator teodorescunicolasteodorescu nicolas alexandru teodorescunicolas Data 28 ianuarie 2023 14:06:10
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.32 kb
#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;
}