Cod sursa(job #2469342)

Utilizator radugheoRadu Mihai Gheorghe radugheo Data 6 octombrie 2019 19:52:10
Problema Cele mai apropiate puncte din plan Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.08 kb
#include <fstream>
#include <iomanip>
#include <cmath>
#include <algorithm>
#include <vector>
#define DIM 100010

using namespace std;

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

long long 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(long long st, long long mid, long long dr) {
    long long i, j, k;
    i = st;
    j = mid + 1;
    k = 0;
    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 (k=1, i=st; i<=dr; i++, k++)
        p[i] = r[k];
}

long long jas(long long st, long long dr){
    long long k;
    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+1], p[dr]), distanta (p[st], p[dr])));
        interclasare (st, st, st+1);
        interclasare (st, st+1, dr);
        return k;
    }
    long long mid = (st + dr)/2;
    long long kst = jas (st, mid);
    long long kdr = jas (mid + 1, dr);
    interclasare (st, mid, dr);
    long long minim = min (kst, kdr);
    long long t = 0;
    for (long long i=st; i<=dr; i++){
        if (abs(p[mid].first - p[i].first) <= minim){
            q[++t] = p[i];
        }
    }
    for (long long i=1; i<t; i++) {
        for (long long 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(make_pair(x,y));
    }
    sort (p.begin(), p.end());
    fout << setprecision(7) << fixed << (double)sqrt(jas(1,n));
    return 0;
}