Cod sursa(job #2462276)

Utilizator LeVladzCiuperceanu Vlad LeVladz Data 26 septembrie 2019 22:59:03
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.55 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<int, int> v[100005],aux[100005];

int dist(pair<int, int> a, pair<int, int> 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];
}

int 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])));
    }
    int sols = solve(st, mid);
    int sold = solve(mid+1, dr);
    int sol = min(sols, sold);
    interclasare(st, mid, dr);
    for (int i=st; i<dr; i++)
        for (int j=i+1; j<=max(dr, i+7); j++)
            sol = min(sol, dist(v[i], v[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;
}