Cod sursa(job #3349528)

Utilizator tudcellTudor Sabau tudcell Data 31 martie 2026 11:10:58
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.4 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;

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

struct Point {
    long long x, y;
};

bool cmpX(const Point& a, const Point& b) {
    if (a.x != b.x) return a.x < b.x;
    return a.y < b.y;
}

bool cmpY(const Point& a, const Point& b) {
    if (a.y != b.y) return a.y < b.y;
    return a.x < b.x;
}

long long dist2(const Point& a, const Point& b) {
    long long dx = a.x - b.x;
    long long dy = a.y - b.y;
    return dx * dx + dy * dy;
}

long long divideEtImpera(vector<Point>& p, int st, int dr) {
    if (dr - st <= 3) {
        long long ans = (1LL << 62);

        for (int i = st; i <= dr; i++) {
            for (int j = i + 1; j <= dr; j++) {
                ans = min(ans, dist2(p[i], p[j]));
            }
        }

        sort(p.begin() + st, p.begin() + dr + 1, cmpY);
        return ans;
    }

    int mid = (st + dr) / 2;
    long long xMid = p[mid].x;

    long long dSt = divideEtImpera(p, st, mid);
    long long dDr = divideEtImpera(p, mid + 1, dr);
    long long d = min(dSt, dDr);

    vector<Point> interclasat;
    interclasat.reserve(dr - st + 1);

    int i = st, j = mid + 1;
    while (i <= mid && j <= dr) {
        if (cmpY(p[i], p[j])) {
            interclasat.push_back(p[i]);
            i++;
        } else {
            interclasat.push_back(p[j]);
            j++;
        }
    }

    while (i <= mid) {
        interclasat.push_back(p[i]);
        i++;
    }

    while (j <= dr) {
        interclasat.push_back(p[j]);
        j++;
    }

    for (int k = 0; k < (int)interclasat.size(); k++) {
        p[st + k] = interclasat[k];
    }

    vector<Point> banda;
    for (int k = st; k <= dr; k++) {
        long long dx = p[k].x - xMid;
        if (dx * dx <= d) {
            banda.push_back(p[k]);
        }
    }

    for (int i = 0; i < (int)banda.size(); i++) {
        for (int j = i + 1; j < (int)banda.size() && j <= i + 7; j++) {
            d = min(d, dist2(banda[i], banda[j]));
        }
    }

    return d;
}

int main() {
    int n;
    fin >> n;

    vector<Point> p(n);
    for (int i = 0; i < n; i++) {
        fin >> p[i].x >> p[i].y;
    }

    sort(p.begin(), p.end(), cmpX);

    long long ans2 = divideEtImpera(p, 0, n - 1);
    long double ans = sqrt((long double)ans2);

    fout << fixed << setprecision(6) << (double)ans << '\n';
    return 0;
}