Cod sursa(job #2769568)

Utilizator Edyci123Bicu Codrut Eduard Edyci123 Data 16 august 2021 18:28:39
Problema Cele mai apropiate puncte din plan Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.72 kb
#include <bits/stdc++.h>
#define NMAX 100005
#define ll long long

using namespace std;

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

int n;
vector <pair <ll, ll>> P;
pair <ll, ll> R[NMAX];

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

void interclasare(int st, int mid, int dr)
{
    int i = st, j = mid + 1, k = st - 1;
    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(int i = st; i <= dr; i++)
        P[i] = R[i];
}

long long cmap(int st, int dr)
{
    if(dr - st == 1)
    {
        interclasare(st, st, dr);
        return dist(P[st], P[dr]);
    }
    if(dr - st == 2)
    {
        long long rez = min(dist(P[st], P[st + 1]), min(dist(P[st], P[dr]), dist(P[st + 1], P[dr])));
        interclasare(st, st, st + 1);
        interclasare(st, st + 1, dr);
        return rez;
    }

    int mid = (st + dr) / 2;
    long long rezSt = cmap(st, mid);
    long long rezDr = cmap(mid + 1, dr);

    interclasare(st, mid, dr);

    long long rez = min(rezSt, rezDr);
    for(int i = st; i < dr; i++)
        for(int j = i + 1; j <= dr && j <= i + 7; j++)
            rez = min(rez, dist(P[i], P[j]));

    return rez;
}

int main()
{
    f >> n;
    for(int i = 1; i <= n; i++)
    {
        ll x, y;
        f >> x >> y;
        P.push_back(make_pair(x, y));
    }
    sort(P.begin(), P.end());

    g << setprecision(7) << fixed << (long double)sqrt(cmap(1, n));
    return 0;
}