Cod sursa(job #3307155)

Utilizator Nasa1004Ema Nicole Gheorghe Nasa1004 Data 18 august 2025 14:05:00
Problema Cele mai apropiate puncte din plan Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.57 kb
#include <fstream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <iomanip>

using namespace std;
const int NMAX = 100000;
using ll = long long;

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

struct puncte{
    ll x, y;
    bool operator <(const puncte & rhs) const {
        if(x != rhs.x)
            return x < rhs.x;
        return x < rhs.y;
    }
}v[NMAX + 2];

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

long double ans = 2e9 * sqrt(2);

long double dist(puncte a, puncte b) {
    return 1LL * sqrt(1LL * (a.x - b.x) * (a.x - b.x) + 1LL * (a.y - b.y) * (a.y - b.y));
}

void divide(int st, int dr) {
    if(st + 1 >= dr) {
        if(st + 1 == dr)
            ans = min(ans, dist(v[st], v[dr]));
        return;
    }
    int mid = (st + dr) / 2;
    divide(st, mid);
    divide(mid + 1, dr);
    vector <puncte> nou; ///DE SCHIMBAT FARA SORTARE
    for(int i = st; i <= dr; i++) {
        if((v[i].x <= v[mid].x && v[i].x + ans <= v[mid].x) ||
            (v[i].x >= v[mid].x && v[i].x - ans <= v[mid].x))
            nou.push_back(v[i]);
    }
    sort(nou.begin(), nou.end(), cmp);
    long double d = ans;
    for(int i = 0; i < nou.size(); i++) {
        for(int j = i + 1; j < min((int)nou.size(), i + 7); j++) { ///doar urm 7
            d = min(d, dist(nou[i], nou[j]));
        }
    }
}
int main() {
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> v[i].x >> v[i].y;
    sort(v + 1, v + n + 1);
    divide(1, n);
    cout << setprecision(6) << fixed << ans;
    return 0;
}