Cod sursa(job #2298208)

Utilizator akaprosAna Kapros akapros Data 7 decembrie 2018 18:41:56
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.33 kb
#include <bits/stdc++.h>
#define maxN 100002
#define ll long long
#define inf 0x3fffffff
using namespace std;

FILE *fin = freopen("cmap.in", "r", stdin);
FILE *fout = freopen("cmap.out", "w", stdout);

int n;
struct Point
{
    int x, y;
    bool operator < (const Point &ot) const
    {
        if (x == ot.x)
            return y < ot.y;
        return x < ot.x;
    }
} v[maxN];
set < Point > s;

ll sqr(int x)
{
    return 1LL * x * x;
}
double dist(Point a, Point b)
{
    return sqrt(sqr(a.x - b.x) + sqr(a.y - b.y));
}
double h;

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; ++ i)
        scanf("%d%d", &v[i].x, &v[i].y);
    auto it = 0;
    sort(v, v + n);
    h = dist(v[0], v[1]);
    for (int i = 0; i < n; ++ i)
    {
        while (it < i && h <= (double)v[i].x - v[it].x)
        {
            s.erase(s.find(Point{v[it].y, v[it].x}));
            ++ it;
        }
        int H = (int)(h);
        auto it1 = s.lower_bound(Point{v[i].y - H,-inf}),
             it2 = s.upper_bound(Point{v[i].y + H, inf});
        if (it2 != s.begin() && it1 != s.end())
        {
            for (auto j = it1; j != it2; ++ j)
                h = min(h, dist(v[i], Point{it1->y, it1->x}));
        }
        s.insert(Point{v[i].y, v[i].x});
    }

    printf("%.7lf", h);
    return 0;
}