Cod sursa(job #2232156)

Utilizator Constantin.Dragancea Constantin Constantin. Data 17 august 2018 16:13:03
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include <bits/stdc++.h>
using namespace std;
typedef long double ld;

#define px second
#define py first
typedef pair<long long, long long> pairll;
bool compare(pairll a, pairll b){return a.px<b.px;}
double ans = 2*(1e9);
pairll a[100010];
int n;
set <pairll> box;

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    ifstream cin ("cmap.in");
    ofstream cout ("cmap.out");
    cin >> n;
    for (int i=1; i<=n; i++) cin >> a[i].py >> a[i].px;
    sort(a+1, a+1+n, compare);
        box.insert(a[1]);
        int left = 1;
        for (int i=2; i<=n; ++i){
            while (left<i && a[i].px - a[left].px > ans)
                box.erase(a[left++]);
            for(set<pairll>::iterator it=box.lower_bound({a[i].py - ans, a[i].px - ans}); it!=box.end() && a[i].py + ans >= it->py; it++)
                ans = min(ans, sqrt(pow(a[i].py - it->py, 2.0)+pow(a[i].px - it->px, 2.0)));
            box.insert(a[i]);
        }
    cout << fixed << setprecision(6) << ans;
    return 0;
}