Cod sursa(job #3120870)

Utilizator redstonegamer22Andrei Ion redstonegamer22 Data 9 aprilie 2023 00:35:32
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.22 kb
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

using namespace std;

#ifndef LOCAL
ifstream in("cmap.in");
ofstream out("cmap.out");
#define cin in
#define cout out
#endif // LOCAL

struct pt {
    int x, y;
};

bool cmp_x(pt a, pt b) {
    if(a.x != b.x) return a.x < b.x;
    return a.y < b.y;
}

bool cmp_y(pt a, pt b) {
    if(a.y != b.y) return a.y < b.y;
    return a.x < b.x;
}

int64_t euclid(pt a, pt b) {
    return (1LL * a.x - b.x) * (1LL * a.x - b.x) + (1LL * a.y - b.y) * (1LL * a.y - b.y);
}

int64_t line_dist(pt a, int d) {
    return (1LL * a.x - d) * (1LL * a.x - d);
}

const int64_t max_dist = 8e18 + 17;
int64_t dist = max_dist;

const int BULAN = 7;

vector<pt> merge_y(vector<pt> a, vector<pt> b) {
    vector<pt> ret;
    std::merge(a.begin(), a.end(),
               b.begin(), b.end(),
               std::back_inserter(ret),
               cmp_y);
    return ret;
}

vector<pt> solve(vector<pt> pts) {
    if(pts.size() <= BULAN) {
        for(int i = 0; i < pts.size(); i++) {
            for(int j = i + 1; j < pts.size(); j++) {
                dist = min(dist, euclid(pts[i], pts[j]));
            }
        }
        sort(pts.begin(), pts.end(), cmp_y);
        return pts;
    }

    int mid = pts.size() / 2;
    vector<pt> lpt, rpt;
    for(int l = 0; l < mid; l++) lpt.push_back(pts[l]);
    for(int r = mid; r < pts.size(); r++) rpt.push_back(pts[r]);

    int dif_x = lpt.back().x;

    lpt = solve(lpt); rpt = solve(rpt);
    pts = merge_y(lpt, rpt);

    vector<pt> close_line;
    for(auto e : pts) if(line_dist(e, dif_x) <= dist) close_line.push_back(e);

    for(int i = 0; i < close_line.size(); i++) {
        for(int j = i + 1; j <= i + BULAN && j < close_line.size(); j++) {
            dist = min(dist, euclid(close_line[i], close_line[j]));
        }
    }

    return pts;
}

int main()
{
    #ifndef LOCAL
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    #endif // LOCAL

    int n; cin >> n;
    vector<pt> v(n); for(auto &e : v) cin >> e.x >> e.y;

    sort(v.begin(), v.end(), cmp_x);
    auto _discard = solve(v);
    cout << fixed << setprecision(8) << sqrt(dist) << endl;

    return 0;
}