Cod sursa(job #2870918)

Utilizator stefan.popescuPopescu Stefan stefan.popescu Data 12 martie 2022 18:28:33
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.64 kb
#include <bits/stdc++.h>

using namespace std;

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

const int nmax = 1e5;
const long long inf = 1e18;
int n;

using Pii = pair<int, int>;

Pii a[nmax + 2];

long long dist(const Pii & p1, const Pii & p2){
    return 1LL * (p1.first - p2.first) * (p1.first - p2.first) + 1LL * (p1.second - p2.second) * (p1.second - p2.second);
};

struct cmp{
    bool operator()(const Pii & p1, const Pii & p2){
        if(p1.second == p2.second)
            return p1.first < p2.first;
        else
            return p1.second < p2.second;
    }
};
Pii temp[nmax + 2];
long long divide(Pii * a, int n){
    long long ans = inf;
    if(n <= 3){
        sort(a, a + n, cmp());
        for(int i = 0; i < n; i++)
            for(int j = i + 1; j < n; j++)
                ans = min(ans, dist(a[i], a[j]));
        return ans;
    }
    if(a[0].first == a[n - 1].first){
        for(int i = 0; i < n - 1; i++)
            ans = min(ans, dist(a[i], a[i + 1]));
        return ans;
    }
    int m = n / 2, xx = a[m].first;
    ans = min(ans, divide(a, m));
    ans = min(ans, divide(a + m, n - m));
    merge(a, a + m, a + m, a + n, temp, cmp());
    memcpy(a, temp, n * 8);
    m = 0;
    for(int i = 0; i < n; i++)
        if(abs(a[i].first - xx) <= ans)
            temp[m++] = a[i];
    for(int i = 0; i < m; i++)
        for(int j = 1; j <= 7 && i + j < m; j++)
            ans = min(ans, dist(a[i], a[i + j]));

    return ans;
}

int main()
{
    in >> n;
    for(int i = 1; i <= n; i++)
        in >> a[i].first >> a[i].second;
    sort(a + 1, a + n + 1);
    out << fixed << setprecision(6) << sqrt(divide(a + 1, n)) << "\n";
    return 0;
}