Cod sursa(job #2462373)

Utilizator LeVladzCiuperceanu Vlad LeVladz Data 27 septembrie 2019 10:37:43
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.83 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <cmath>
#define xx first
#define yy second

using namespace std;

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

int n,i;
pair<long long, long long> v[100005],aux[100005];

long long dist(pair<long long, long long> a, pair<long long, long long> b)
{ return (a.xx-b.xx)*(a.xx-b.xx)+(a.yy-b.yy)*(a.yy-b.yy); }

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

long long solve(int st, int dr)
{
    int mid = (st+dr)/2;
    if (dr-st == 1)
    {
        interclasare(st, mid, dr);
        return dist(v[st], v[dr]);
    }
    if (dr-st == 2)
    {
        interclasare(st, st, mid); interclasare(st, mid, dr);
        return min(dist(v[st+1], v[st+2]), min(dist(v[st], v[st+1]), dist(v[st], v[st+2])));
    }
    long long sols = solve(st, mid);
    long long sold = solve(mid+1, dr);
    long long sol = min(sols, sold);
    interclasare(st, mid, dr);
    int k = 0;
    for (int i=st; i<=mid; i++)
        if (v[mid].xx-v[i].xx <= sol)
            aux[++k] = v[i];
    for (int i=mid+1; i<=dr; i++)
        if (v[i].xx-v[mid].xx <= sol)
            aux[++k] = v[i];
    for (int i=1; i<k; i++)
        for (int j=i+1; j<=min(k, i+7); j++)
            sol = min(sol, dist(aux[i], aux[j]));
    return sol;
}

int main()
{
    fin >> n;
    for (i=1; i<=n; i++)
        fin >> v[i].xx >> v[i].yy;
    sort(v+1, v+n+1);
    fout << setprecision(7) << fixed << sqrt(solve(1, n));
    return 0;
}