Cod sursa(job #1671626)

Utilizator cosmin79Carabet Cosmin Andrei cosmin79 Data 1 aprilie 2016 22:46:35
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
#include <cstdio>
#include <algorithm>
#include <set>
#include <cmath>
#define x first
#define y second
#define pii pair<int, int>
using namespace std;

const int NMAX = 100505;
const long long INF = (1LL << 61);

int N;
pii P[NMAX];

void read() {
    scanf("%d", &N);
    for (int i = 1; i <= N; i++) {
        scanf("%d%d", &P[i].x, &P[i].y);
    }
}

long long dist(pii& a, pii& b) {
    return 1LL * (a.x - b.x) * (a.x - b.x) + 
        1LL * (a.y - b.y) * (a.y - b.y);
}

void solve() {
    sort(P + 1, P + N + 1);
    long long h = INF;

    set <pair<int, int>> pts;
    pts.insert({P[1].y, 1});
    int idx = 1;
    for (int i = 2; i <= N; i++) {
        while (idx < i && 1LL * (P[i].x - P[idx].x) * (P[i].x - P[idx].x) > h) {
            pts.erase({P[idx].y, idx});
            idx++;
        }

        int hh = (int)sqrt((double)h);
        auto it1 = pts.lower_bound({P[i].y - hh, -1});
        auto it2 = pts.upper_bound({P[i].y + hh, -1});
        if (it1 != pts.end()) {
            for (auto it = it1; it != it2; it++) {
                h = min(h, dist(P[i], P[it -> second]));
            }
        }

        pts.insert({P[i].y, i});
    }

    printf("%.10lf\n", sqrt(double(h)));
}

int main() {
    freopen("cmap.in", "r", stdin);
    freopen("cmap.out", "w", stdout);

    read();
    solve();
    return 0;
}