Cod sursa(job #3198333)

Utilizator Radu_MocanasuMocanasu Radu Radu_Mocanasu Data 28 ianuarie 2024 21:49:02
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.63 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
struct point{
    int x,y;
    bool operator<(const point &other){
        return this->x < other.x;
    }
}v[100005];
point v2[100005];
int dist(const point &a, const point &b){
    return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}
int solve(int st, int dr){
    if(dr - st <= 3){
        int m = dist(v[st], v[st + 1]);
        for(int i = st; i <= dr; i++){
            for(int j = i + 1; j <= dr; j++){
                m = min(m, dist(v[i], v[j]));
            }
        }
        for(int i = st; i <= dr; i++){
            for(int j = i + 1; j <= dr; j++){
                if(v[i].y > v[j].y) swap(v[i], v[j]);
            }
        }
        return m;
    }
    int med = (st + dr) >> 1,k = 0,t = 0;
    int i,m = solve(st, med), k1 = st, k2 = med + 1, l = v[med].x;
    m = min(m, solve(med + 1, dr));
    while(k1 <= med && k2 <= dr){
        if(v[k1].y < v[k2].y) v2[++k] = v[k1++];
        else v2[++k] = v[k2++];
    }
    while(k1 <= med) v2[++k] = v[k1++];
    while(k2 <= dr) v2[++k] = v[k2++];
    for(i = st; i <= dr; i++) v[i] = v2[i - st + 1];
    for(i = st; i <= dr; i++){
        if((v[i].x - l) * (v[i].x - l) <= m) v2[++t] = v[i];
    }
    for(i = 1; i <= t; i++){
        for(int j = i + 1; j <= min(i + 7, t); j++) m = min(m, dist(v[i], v[j]));
    }
    return m;
}
int main()
{
    int n,i;
    fin >> n;
    for(i = 1; i <= n; i++) fin >> v[i].x >> v[i].y;
    sort(v + 1, v + n + 1);
    fout << fixed << setprecision(6);
    fout << sqrt(solve(1,n));
    return 0;
}