Cod sursa(job #2495154)

Utilizator mihaidanielmihai daniel mihaidaniel Data 18 noiembrie 2019 22:04:32
Problema Cele mai apropiate puncte din plan Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.69 kb
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdint>
using namespace std;

FILE* in  = fopen ("cmap.in",  "r");
FILE* out = fopen ("cmap.out", "w");

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;
    fscanf (in, "%d", &n);
    v.resize(n);
    w.resize(n);
    for (int i = 0; i < n; ++ i)
    {
        fscanf (in, "%I64d%I64d", &v[i].first, &v[i].second);
    }
    fclose (in);

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

    fprintf (out, "%.6f", sqrt(rec(0, n)));
    fclose (out);
    return 0;
}