Cod sursa(job #2285919)

Utilizator theodor.moroianuTheodor Moroianu theodor.moroianu Data 19 noiembrie 2018 15:19:10
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.66 kb
#include <bits/stdc++.h>
#define p2(x) 1LL * (x) * (x)
using namespace std;

typedef long long i64;

set <pair <int, int>> sline;
vector <pair <int, int>> points;
i64 distact = 1e18;
int until;

inline void pass(int poz)
{
    while (1) {
        int dist = points[poz].first - points[until].first;
        if (p2(dist) >= distact) {
            sline.erase({ points[until].second, until });
            until++;
        }
        else
            break;
    }
}

int main()
{
    FILE *in = fopen("cmap.in", "r");
    ofstream out("cmap.out");

    int n;
    fscanf(in, "%d", &n);

    points.resize(n);

    for (auto & i : points)
        fscanf(in, "%d%d", &i.first, &i.second);

    sort(points.begin(), points.end());
    until = 0;
    sline.insert({ points[0].second, 0 });

    for (int i = 1; i < n; i++) {
        auto x = sline.lower_bound({ points[i].second, 0 });
        while (x != sline.end()) {
            i64 d = p2(points[i].second - x->first);
            if (d > distact)
                break;
            d += p2(points[i].first - points[x->second].first);
            distact = min(distact, d);
            x++;
        }
        x = sline.lower_bound({ points[i].second, 0 });
        while (x != sline.begin()) {
            x--;
            i64 d = p2(points[i].second - x->first);
            if (d > distact)
                break;
            d += p2(points[i].first - points[x->second].first);
            distact = min(distact, d);
        }
        sline.insert({ points[i].second, i });
        pass(i);
    }

    out << setprecision(9) << fixed << sqrt(distact) << '\n';

    return 0;
}