Cod sursa(job #2954685)

Utilizator Tudor06MusatTudor Tudor06 Data 15 decembrie 2022 00:38:12
Problema Cele mai apropiate puncte din plan Scor 95
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.29 kb
#include <bits/stdc++.h>

using namespace std;

const int NMAX = 1e5;
const double INF = 4e9;

struct point {
    int x;
    int y;
} v[NMAX + 1];

static inline double dist( point a, point b ) {
    return sqrtl( (long long)( a.x - b.x ) * ( a.x - b.x ) +
                  (long long)( a.y - b.y ) * ( a.y - b.y ) );
}
static inline int modul( int x ) {
    if ( x < 0 ) return -x;
    return x;
}
double cmap( int st, int dr ) {
    if ( dr - st + 1 <= 3 ) {
        double dmin = INF;
        for ( int i = st; i <= dr; i ++ ) {
            for ( int j = i + 1; j <= dr; j ++ ) {
                if ( v[i].y > v[j].y ) {
                    swap( v[i], v[j] );
                }
                dmin = min( dmin, dist( v[i], v[j] ) );
            }
        }
        return dmin;
    }
    int mij = ( st + dr ) / 2;
    double dmin = min( cmap( st, mij ), cmap( mij + 1, dr ) );
    vector <point> intercls;
    vector <point> useful;
    int i = st, j = mij + 1;
    while ( i <= mij && j <= dr ) {
        point aux;
        if ( v[i].y < v[j].y ) {
            aux = v[i++];
        } else {
            aux = v[j++];
        }
        if ( modul( aux.x - v[mij].x ) <= dmin ) {
            useful.push_back( aux );
        }
        intercls.push_back( aux );
    }
    for ( ; i <= mij; i ++ ) {
        if ( modul( v[i].x - v[mij].x ) <= dmin )
            useful.push_back( v[i] );
        intercls.push_back( v[i] );
    }
    for ( ; j <= dr; j ++ ) {
        if ( modul( v[j].x - v[mij].x ) <= dmin )
            useful.push_back( v[j] );
        intercls.push_back( v[j] );
    }
    for ( int i = st; i <= dr; i ++ ) {
        v[i] = intercls[i - st];
    }
    for ( int i = 0; i < useful.size(); i ++ ) {
        int till = min( i + 10, (int)useful.size() );
        for ( int j = i + 1; j < till; j ++ ) {
            dmin = min( dmin, dist( useful[i], useful[j] ) );
        }
    }
    return dmin;
}
int main() {
    ifstream fin( "cmap.in" );
    ofstream fout( "cmap.out" );
    int n;
    fin >> n;
    for ( int i = 1; i <= n; i ++ ) {
        fin >> v[i].x >> v[i].y;
    }
    sort( v + 1, v + n + 1, []( point a, point b ) {
        return a.x < b.x;
    });
    fout << fixed << setprecision( 7 ) << cmap( 1, n );
    return 0;
}