Cod sursa(job #3213075)

Utilizator sandry24Grosu Alexandru sandry24 Data 12 martie 2024 14:16:17
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.35 kb
#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O2,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pi;
#define pb push_back
#define mp make_pair
#define f first
#define s second

void solve(){
    int n;
    cin >> n;
    vector<pi> pts(n);
    for(int i = 0; i < n; i++)
        cin >> pts[i].f >> pts[i].s;
    sort(pts.begin(), pts.end());
    double d = 1e12;
    int j = 0;
    set<pair<ll, ll>> s; //set {y, x};
    for(int i = 0; i < n; i++){
        while(pts[i].f - pts[j].f >= d){
            s.erase({pts[j].s, pts[j].f});
            j++;
        }
        auto l = s.lower_bound({ll(pts[i].s - ceil(d)), pts[i].f});
        auto r = s.upper_bound({ll(pts[i].s + ceil(d)), pts[i].f});
        for(auto it = l; it != r; ++it){
            ll diffx = pts[i].f - it->second;
            ll diffy = pts[i].s - it->first;
            double dist = sqrtl(diffx*diffx + diffy*diffy);
            d = min(d, dist);
        }
        s.insert({pts[i].s, pts[i].f});
    }
    cout << fixed << setprecision(6) << d << '\n';
}   

int main(){
    freopen("cmap.in", "r", stdin);
    freopen("cmap.out", "w", stdout);
    ios::sync_with_stdio(0); cin.tie(0);
    int t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
}