Cod sursa(job #2232161)

Utilizator Constantin.Dragancea Constantin Constantin. Data 17 august 2018 16:23:07
Problema Cele mai apropiate puncte din plan Scor 25
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef pair <int,int> pii;

#define x first
#define y second
int n, st = 1;
pii a[100010];
set<pii> S;
double ans = 2*(1e9);

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

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