Cod sursa(job #2495137)

Utilizator mihaidanielmihai daniel mihaidaniel Data 18 noiembrie 2019 21:53:58
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.62 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

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

vector < pair <uint64_t, uint64_t> > v, w;

uint64_t dist (const pair <uint64_t, uint64_t>& a, const pair <uint64_t, uint64_t>& b)
{
    return (a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second);
}

uint64_t rec(int st, int dr)
{
    if (dr - st <= 1) {return 0xffffff;}
    if (dr - st == 2) {return dist(v[st], v[dr - 1]);}
    if (dr - st == 3) {return max (dist(v[st], v[st+1]), max(dist(v[st], v[st+2]), dist(v[st+1], v[st+2])));}
    int mid = (st + dr) / 2, i = st, j = mid, nr = st;
    uint64_t ret = min(rec(st, mid), rec(mid, dr));

    while (i < mid && j < dr)
    {
        if (w[i] < w[j]) {w[nr++] = v[i++];}
        else             {w[nr++] = v[j++];}
    }
    while (i < mid) {w[nr++] = v[i++];}
    while (j < dr)  {w[nr++] = v[j++];}

    nr = 0;
    mid = w[mid].first;
    for (i = st; i < dr; ++i)
    {
        if (abs(v[i].second - mid) <= ret)
        {
            w[nr++] = v[i];
        }
    }
    for (i = 0; i < nr - 1; ++i)
    {
        for (j = i + 1; j < nr && j - i < 8; ++j)
        {
            ret = min(ret, dist(w[i], w[j]));
        }
    }
    return ret;
}

int main(void)
{
    int n;
    in >> n;
    v.resize(n);
    w.resize(n);
    for (int i = 0; i < n; ++ i)
    {
        in >> v[i].first >> v[i].second;
    }
    in.close();

    sort(v.begin(), v.end());

    cout << sqrt(rec(0, n)) << "\n";
    out.close();
    return 0;
}