Cod sursa(job #2465355)

Utilizator radugheoRadu Mihai Gheorghe radugheo Data 29 septembrie 2019 22:27:07
Problema Cele mai apropiate puncte din plan Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.93 kb
#include <bits/stdc++.h>
#define DIM 100005

using namespace std;

ifstream fin  ("cmap.in");
ofstream fout ("cmap.out");

int n, i, x, y;

vector <pair <long long, long long> > p;

pair <long long, long long> r[DIM], q[DIM];

long long distanta (pair <long long, long long> a, pair <long long, long long> b){
    return (a.first - b.first)*(a.first - b.first) + (a.second - b.second)*(a.second - b.second);
}

void interclasare(int st, int mid, int dr) {
    int i, j, k;
    i = st;
    j = mid + 1;
    k = st - 1;
    while (i<=mid && j<=dr)
        if (p[i].second < p[j].second) {
            r[++k] = p[i++];
        } else {
            r[++k] = p[j++];
        }
    for (; i<=mid; i++)
        r[++k] = p[i];
    for (; j<=dr; j++)
        r[++k] = p[j];
    for (i=st; i<=dr; i++)
        p[i] = r[i];
}

long long jas(int st, int dr){
    long long i, j, k = 0, t = 0, kst = 0, kdr = 0, minim;
    if (dr - st == 1){
        k = distanta (p[st], p[dr]);
        interclasare (st, st, dr);
        return k;
    }
    if (dr - st == 2){
        k = min (distanta (p[st], p[st+1]), min(distanta (p[st], p[st+2]), distanta (p[st+1], p[st+2])));
        interclasare (st, st, st+1);
        interclasare (st, st+1, dr);
        return k;
    }
    int mid = (st + dr)/2;
    kst = jas (st, mid);
    kdr = jas (mid + 1, dr);
    interclasare (st, mid, dr);
    minim = min (kst, kdr);
    t = 0;
    for (i=st; i<=dr; i++){
        if (abs(p[mid].first - p[i].first) <= minim){
            q[++t] = p[i];
        }
    }
    for (i=1; i<t; i++) {
        for (j=i+1; j<=t && j<=i+7; j++)
            minim = min (minim, distanta(q[i], q[j]));
    }
    return minim;
}

int main(){
    fin >> n;
    for (i=1; i<=n; i++){
        fin >> x >> y;
        p.push_back({x, y});
    }
    sort (p.begin(), p.end());
    fout << setprecision(6) << fixed << (double)sqrt(jas(1,n));
    return 0;
}