Cod sursa(job #2969245)

Utilizator Andrei_ierdnANeculau Rares-Andrei Andrei_ierdnA Data 22 ianuarie 2023 19:13:26
Problema Cele mai apropiate puncte din plan Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.8 kb
#include <bits/stdc++.h>

using namespace std;

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

#define ll long long

ll n, i, mindist = __LONG_LONG_MAX__;

struct Punct
{
    int x, y;
} v[100100], v2[100100];

deque<int> squareCheck;
deque<int>::iterator it;

bool xComp(const Punct &a, const Punct &b)
{
    if (a.x < b.x)
        return true;
    if (a.x == b.x)
        if (a.y < b.y)
            return true;
    return false;
}

bool yComp(const Punct &a, const Punct &b)
{
    if (a.y < b.y)
        return true;
    if (a.y == b.y)
        if (a.x < b.x)
            return true;
    return false;
}

ll getDist(const Punct &a, const Punct &b)
{
    return ((long long)(a.x - b.x)) * (a.x - b.x) + ((long long)(a.y - b.y)) * (a.y - b.y);
}

void mergeDist(int vst, int vdr, int &maxx, Punct *oldv, Punct *newv)
{
    if (vst >= vdr-2) {
        for (int i = vst; i < vdr; i++) {
            for (int j = i+1; j <= vdr; j++) {
                mindist = min(mindist, getDist(oldv[i], oldv[j]));
                if (oldv[i].y > oldv[j].y)
                    swap(newv[i], newv[j]);
            }
        }
        for (int i = vst; i <= vdr; i++)
            maxx = max(maxx, int(oldv[i].x));
        return;
    }
    int max1 = -INT_MAX, max2 = -INT_MAX, mij = (vst+vdr)/2, aux = mindist;
    mergeDist(vst, mij, max1, newv, oldv);
    mergeDist(mij+1, vdr, max2, newv, oldv);
    maxx = max(max1, max2);
    int st = mij+1;
    int dr = mij;
    for (int j = vst; j <= mij; j++) {
        while (dr < vdr && oldv[dr+1].y <= oldv[j].y + aux) {
            dr++;
            if (oldv[dr].x <= max1 + aux) {
                squareCheck.push_back(dr);
            }
        }
        while (st <= vdr && oldv[st].y < oldv[j].y - aux) {
            if (squareCheck.front() == st)
                squareCheck.pop_front();
            st++;
        }
        for (it = squareCheck.begin(); it != squareCheck.end(); advance(it, 1))
        {
            mindist = min(mindist, getDist(oldv[j], oldv[(*it)]));
        }
    }
    while (!squareCheck.empty())
        squareCheck.pop_front();
    int k = vst, i = vst, j = mij+1;
    while (i <= mij && j <= vdr) {
        if (oldv[i].y <= oldv[j].y) {
            newv[k++] = oldv[i++];
        }
        else {
            newv[k++] = oldv[j++];
        }
    }
    while (i <= mij)
        newv[k++] = oldv[i++];
    while (j <= vdr)
        newv[k++] = oldv[j++];
}

int main()
{
    f >> n;
    for (i = 1; i <= n; i++) {
        f >> v[i].x >> v[i].y;
    }
    sort(v+1, v+n+1, xComp);
    for (i = 1; i <= n; i++)
        v2[i] = v[i];
    int aux = 0;
    mergeDist(1, n, aux, v, v2);
    g << std::fixed << setprecision(6);
    g << sqrt(mindist);
    f.close();
    g.close();
    return 0;
}