Cod sursa(job #2426977)

Utilizator Alex18maiAlex Enache Alex18mai Data 30 mai 2019 11:43:29
Problema Cele mai apropiate puncte din plan Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.2 kb
//ALEX ENACHE

#include <vector>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <unordered_map>
#include <time.h>
#include <iomanip>
#include <deque>
#include <math.h>
#include <cmath>
#include <assert.h>
#include <stack>
#include <bitset>
#include <random>
#include <chrono>

using namespace std;

const double PI = acos(-1);
const double eps = 1e-6;

inline long long lgput(long long a , long long b , long long mod) {
    long long ret = 1;
    while( b ){
        if(b & 1) ret = (ret * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }

    return (ret%mod);
}

inline long long inv(long long x , long long MOD) {
    return lgput(x, MOD - 2, MOD);
}

inline bool exist (double nr){
    return (nr < -eps) || (nr > eps);
}

long long big_rand(){
    return rand () * RAND_MAX + rand();
}

//-----------------------------------------------------------------

//#include <iostream>
#include <fstream>
ifstream cin ("cmap.in");ofstream cout ("cmap.out");

struct nod{long long x , y;};
bool cmpx (nod a , nod b){return a.x < b.x;}
bool cmpy (nod a , nod b){return a.y < b.y;}
nod v[100100] , ord[100100];

double dist (nod a , nod b){
    double now = (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y);
    return sqrt(now);
}

double solve (int st , int dr){

    double ans = 1e18;
    if (dr-st+1 <= 3){
        for (int i=st; i<=dr; i++){
            for (int j=i+1; j<=dr; j++){
                ans = min(ans , dist(v[i] , v[j]));
            }
        }
        sort (v+st , v+dr+1 , cmpy);
        return ans;
    }

    int mij = st + dr;
    mij /= 2;
    long long middle = v[mij].x;
    double low = min(solve(st , mij) , solve(mij+1 , dr));

    int ST = st , DR = mij+1 , pnt = st;
    while (ST <= mij && DR <= dr){
        //cout<<v[ST].y<<" "<<v[DR].y<<'\n';
        if (v[ST].y < v[DR].y){
            ord[pnt++] = v[ST++];
        }
        else{
            ord[pnt++] = v[DR++];
        }
    }
    for (; ST<=mij; ST++)ord[pnt++]=v[ST];
    for (; DR<=dr; DR++)ord[pnt++]=v[DR];
    //cout<<st<<" "<<dr<<" "<<mij<<" ; "<<ST<<" "<<DR<<" "<<pnt<<'\n';
    for (int i=st; i<=dr; i++){
        //cout<<ord[i].y<<" ";
        v[i] = ord[i];
    }
    //cout<<'\n';
    pnt = 0;
    for (int i=st; i<=dr; i++){
        if (abs(v[i].x - middle) <= (long long)low){
            ord[++pnt]= v[i];
        }
    }

    ans = low;
    for (int i=1; i<=pnt; i++){
        for (int j=i+1; j<=pnt; j++){
            if (v[j].y - v[i].y > (long long)low){
                break;
            }
            ans = min(ans , dist(ord[i] , ord[j]));
        }
    }

    return ans;
}


int main() {

    //freopen("input", "r", stdin);freopen("output", "w", stdout);

    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cout << setprecision(10) << fixed;
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    srand(time(nullptr));

    int n;
    cin>>n;

    for (int i=1; i<=n; i++){
        int a , b;
        cin>>a>>b;
        v[i].x = a;
        v[i].y = b;
    }
    sort(v+1 , v+n+1 , cmpx);
    cout<<solve (1 , n)<<'\n';

    return 0;
}