Cod sursa(job #2771783)

Utilizator Edyci123Bicu Codrut Eduard Edyci123 Data 29 august 2021 10:34:57
Problema Cele mai apropiate puncte din plan Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.94 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], Q[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)
    {
        long long rez = dist(P[st], P[dr]);
        interclasare(st, st, dr);
        return rez;
    }
    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 xmid = P[mid].first;

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

    interclasare(st, mid, dr);
    long long rez = min(rezSt, rezDr);

    int nrPoints = 0;
    for (int i=st;i<=dr;i++) {
        if ((abs(P[i].first - xmid)) <= sqrt(rez))
            Q[++nrPoints] = P[i];
    }

    for(int i = 1; i < nrPoints; i++)
        for(int j = 1; j <= 7 && i+j<=nrPoints; j++)
            rez = min(rez, dist(Q[i], Q[i+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 << (double)sqrt(cmap(1, n));
    return 0;
}