Cod sursa(job #3307159)

Utilizator Nasa1004Ema Nicole Gheorghe Nasa1004 Data 18 august 2025 14:28:27
Problema Cele mai apropiate puncte din plan Scor 95
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.4 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], ord[NMAX + 2];

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) {
            ///MERGESORT
            if(ord[st].y > ord[dr].y || (ord[st].y == ord[dr].y && ord[st].x > ord[dr].x))
                swap(ord[st], ord[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; ///MERGESORT
    int pos1 = st, pos2 = mid + 1;
    while(pos1 <= mid && pos2 <= dr) {
        if(ord[pos1].y < ord[pos2].x || (ord[pos1].y == ord[pos2].y && ord[pos1].x < ord[pos2].x)) {
            nou.push_back(ord[pos1]);
            pos1++;
        }
        else {
            nou.push_back(ord[pos2]);
            pos2++;
        }
    }
    while(pos1 <= mid) {
        nou.push_back(ord[pos1]);
        pos1++;
    }
    while(pos2 <= dr) {
        nou.push_back(ord[pos2]);
        pos2++;
    }
    for(int i = st; i <= dr; i++) {
        ord[i].x = nou[i - st].x;
        ord[i].y = nou[i - st].y;
    }

    ///INAPOI LA CE PUNCTE AVEM NEVOIE
    nou.clear();
    int lin = v[mid].x; ///ca eu acolo am impartit
    for(int i = st; i <= dr; i++) {
        if((ord[i].x <= lin && ord[i].x + ans <= lin) ||
           (ord[i].x > lin && ord[i].x - ans <= lin))
            nou.push_back(ord[i]);
    }
    long double d = ans;
    for(int i = 0; i < nou.size(); i++) {
        for(int j = i + 1; j < min((int)nou.size(), i + 8); j++) { ///doar urm 7
            d = min(d, dist(nou[i], nou[j]));
        }
    }
    ans = min(ans, d);
}
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);
    for(int i = 1; i <= n; i++) { ///merge sort pt y
        ord[i].x = v[i].x;
        ord[i].y = v[i].y;
    }
    divide(1, n);
    cout << setprecision(6) << fixed << ans;
    return 0;
}