Cod sursa(job #3357810)

Utilizator TestLicenta123Test Test TestLicenta123 Data 13 iunie 2026 15:09:43
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.66 kb
#include <vector>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <unordered_map>
#include <time.h>
#include <iomanip>
#include <deque>
#include <math.h>
#include <cmath>
#include <assert.h>
#include <stack>
#include <bitset>
#include <random>
#include <chrono>

using namespace std;

const double PI = acos(-1);
const double eps = 1e-6;

inline long long lgput(long long a , long long b , long long mod) {
    long long ret = 1;
    while( b ){
        if(b & 1) ret = (ret * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }

    return (ret%mod);
}

inline long long inv(long long x , long long MOD) {
    return lgput(x, MOD - 2, MOD);
}

inline bool exist (double nr){
    return (nr < -eps) || (nr > eps);
}

long long big_rand(){
    return rand () * RAND_MAX + rand();
}

//-----------------------------------------------------------------

#include <fstream>
ifstream cin ("cmap.in"); ofstream cout ("cmap.out");

struct nod {
    int x, y;
};
bool cmpx(nod a, nod b) { return a.x < b.x; }
bool cmpy(nod a, nod b) { return a.y < b.y; }
nod v[100100], ord[100100];

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

double solve(int st, int dr) {
    double ans = 1e18;
    if (dr - st + 1 <= 3) {
        for (int i = st; i <= dr; i++) {
            for (int j = i + 1; j <= dr; j++) {
                ans = min(ans, dist(v[i], v[j]));
            }
        }
        sort(v + st, v + dr + 1, cmpy);
        return ans;
    }

    int mij = (st + dr) / 2;
    int middle = v[mij].x;
    double low = min(solve(st, mij), solve(mij + 1, dr));

    int ST = st, DR = mij + 1, pnt = st;
    while (ST <= mij && DR <= dr) {
        if (v[ST].y < v[DR].y) {
            ord[pnt++] = v[ST++];
        } else {
            ord[pnt++] = v[DR++];
        }
    }
    while (ST <= mij) ord[pnt++] = v[ST++];
    while (DR <= dr) ord[pnt++] = v[DR++];
    for (int i = st; i <= dr; i++) {
        v[i] = ord[i];
    }

    vector<nod> strip;
    for (int i = st; i <= dr; i++) {
        if (abs(v[i].x - middle) <= low) {
            strip.push_back(v[i]);
        }
    }

    ans = low;
    for (int i = 0; i < (int)strip.size(); i++) {
        for (int j = i + 1; j < (int)strip.size() && (strip[j].y - strip[i].y) < ans; j++) {
            ans = min(ans, dist(strip[i], strip[j]));
        }
    }

    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cout << setprecision(6) << fixed;

    int n;
    cin >> n;

    for (int i = 1; i <= n; i++) {
        cin >> v[i].x >> v[i].y;
    }
    sort(v + 1, v + n + 1, cmpx);
    cout << solve(1, n);

    return 0;
}