Cod sursa(job #2446360)

Utilizator ArdeleanOficialAlexandru ArdeleanOficial Data 8 august 2019 00:10:50
Problema Cele mai apropiate puncte din plan Scor 75
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.35 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("cmap.in");
ofstream fout("cmap.out");

const int N = 1e5 + 7;

struct Point {
    int x, y;

    void read() {
        fin >> x >> y;
    }

    bool operator < (const Point &a) const {
        return x < a.x;
    }
};

double distance(Point a, Point b) {
    return sqrt(1.0 * (a.x - b.x) * (a.x - b.x) + 1.0 * (a.y - b.y) * (a.y - b.y));
}

Point v[N];

struct cmp {
    bool operator() (const int &a, const int &b) const {
        return v[a].y < v[b].y;
    }
};

set < int, cmp > s;

int main()
{
    int n;
    fin >> n;
    for (int i = 0; i < n; ++i)
        v[i].read();
    sort(v, v + n);
    double ans(2e9 + 7);
    int j(0);
    ans = distance(v[0], v[1]);
    s.insert(0);
    s.insert(1);
    for (int i = 2; i < n; ++i) {
        while (v[i].x - v[j].x >= ans) {
            s.erase(j);
            ++j;
        }
        v[i].y -= ans;
        auto st = s.lower_bound(i);
        v[i].y += 2 * ans;
        auto dr = s.upper_bound(i);
        v[i].y -= ans;
        while (st != dr) {
            auto x = distance(v[*st], v[i]);///mai putin de scris
            if (ans > x)
                ans = x;
            st = next(st);
        }
        s.insert(i);
    }
    fout << fixed << setprecision(9);
    fout << ans;
    return 0;
}