Cod sursa(job #3001301)

Utilizator TeddyDinutaDinuta Eduard Stefan TeddyDinuta Data 13 martie 2023 14:33:01
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.76 kb
#include <bits/stdc++.h>

using namespace std;
ifstream in("cmap.in");
ofstream out("cmap.out");

struct punct {
    long long x, y;
}v[100005], a[100005], aux[100005];

long long n;

long long distance(punct p1, punct p2) {
    return (p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y);
}

void merge(int l, int r, int m, punct v[]) {
    int i = l, j = m + 1;

    vector<punct> aux;

    while (i <= m && j <= r) {
        if (v[i].y <= v[j].y) aux.push_back(v[i++]);
        else aux.push_back(v[j++]);
    }

    while (i <= m)
        aux.push_back(v[i++]);
    
    while (j <= r)
        aux.push_back(v[j++]);
    
    for (int i = 0; i < aux.size(); i++)
        v[l + i] = aux[i];
}

double solve(long long l, long long r) {
    if (r - l + 1 <= 3) {
        sort(a + l, a + r + 1, [](const punct &p1, const punct &p2) {
            return p1.y < p2.y;
        });
        long long dmin = distance(v[l], v[r]);
        if (l + 1 != r) {
            dmin = min(dmin, min(distance(v[l + 1], v[r]), distance(v[l], v[l + 1])));
        }
        return dmin;
    }

    long long m = (l + r) / 2;
    long long dmin = min(solve(l, m), solve(m, r));

    
    merge(l, r, m, a);

    int k = 0;
    for (int i = l; i <= r; i++)
        if (abs(a[i].x - v[m].x) <= dmin)
            aux[++k] = a[i];
    
    for (int i = 1; i <= k; i++) {
        for (int j = i + 1; j <= k && j - i <= 8; j++)
            dmin = min(dmin, distance(aux[i], aux[j]));
    }

    return dmin;
}

int main() {
   in>>n;
   for (int i = 1; i <= n; i++) {
        in>>v[i].x>>v[i].y;
        a[i] = v[i];
   }
    
    sort(v + 1, v + n + 1, [](const punct &p1, const punct &p2) {
        return p1.x < p2.x || (p1.x == p2.x && p1.y < p2.y);
    });

    out<<fixed<<setprecision(6)<<sqrt(solve(1, n))<<'\n';

}