Cod sursa(job #3148164)

Utilizator ElizaTElla Rose ElizaT Data 29 august 2023 17:00:16
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.6 kb
#include <bits/stdc++.h>

using namespace std;

const int NMAX = 1e5;
const long long INF = 4e18;

vector < pair <long long, long long> > v(NMAX), x, y;

long long dist(const pair <long long, long long>& a, const pair <long long, long long>& b) {
    return (a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second);
}
long long sl(int st, int dr, vector < pair <long long, long long> >& x, vector < pair <long long, long long> >& y) {
    if (st >= dr - 1)
        return INF;
    else if (dr - st == 2) {
        if (y[st] > y[st + 1])
            swap(y[st], y[st + 1]);
        return dist(x[st], x[st + 1]);
    }
    
    int md = (st + dr) / 2;
    long long mn = min(sl(st, md, x, y), sl(md, dr, x, y));
    merge(y.begin() + st, y.begin() + md, y.begin() + md, y.begin() + dr, v.begin());
    copy(v.begin(), v.begin() + (dr - st), y.begin() + st);
    
    int cnt = 0;
    for (int i = st;i < dr;i++) 
        if (abs(y[i].second - x[md].first) <= mn)
            v[cnt++] = y[i];
    for (int i = 0;i < cnt - 1;i++) {
        for (int j = i + 1;j < cnt && j - i < 8;j++)
            mn = min(mn, dist(v[i], v[j]));
    }
    return mn;
}
int main() 
{
    ifstream fin("cmap.in");
    ofstream fout("cmap.out");
    int n;
    fin >> n;
    x.resize(n), y.resize(n);
    for (int i = 0;i < n;i++)
        fin >> x[i].first >> x[i].second;
        
    sort(x.begin(), x.end());
    for (int i = 0;i < n;i++)
        y[i] = make_pair(x[i].second, x[i].first);
    fout << fixed << setprecision(6) << sqrt(sl(0, n, x, y)) << '\n';
    return 0;
}