Cod sursa(job #2232150)

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

#define x first
#define y second
int n, st;
pair <ld, ld> a[100010];
set <pair<ld, ld> > box;
ld ans = 1e9;

ld dist(pair<ld,ld> a, pair<ld,ld> b){
    return sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));
}

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].x >> a[i].y;
    sort(a+1, a+1+n);
    box.insert(a[1]);
    for (int i=2; i<=n; i++){
        while(box.size() && a[i].x - box.begin()->x > ans) box.erase(box.begin());
        for (set<pair<ld,ld> >::iterator it = box.lower_bound({a[i].x - ans, a[i].y - ans}); it != box.end(); it++)
            ans = min(ans, dist(a[i], *it));
        box.insert(a[i]);
    }
    cout << fixed << setprecision(6) << ans;
    return 0;
}