[C++][백준 2261] 가장 가까운 두 점

문제

https://www.acmicpc.net/problem/2261

접근 방법

가장 가까운 두 점의 조건은 다른 두 점보다 짧은 거리에 존재해야 된다는 것입니다.
그렇다면 x값이 정렬된 순서로 살펴볼 때 현재 살펴보는 점 기준에서 가장 짧은 거리 안에 있지 않은 이전 점들은 가장 가까운 두 점이 될 수 있는 조건에서 탈락했다고 볼 수 있습니다.
이후 y값이 정렬된 순서로 살펴볼 때 현재 살펴보는 점 기준에서 가장 짧은 거리 내에 있는 것만 살펴보면 됩니다.

코드

#include <iostream>
#include <set>
#include <cmath>
#include <algorithm>
using namespace std;

using pos = pair<int, int>;

int n;
pos posArr[100000];

void input()
{
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n;
    for (int i = 0; i < n; ++i)
    {
        cin >> posArr[i].first >> posArr[i].second;
    }
}

int calcDistSq(const pos &a, const pos &b)
{
    int dx = a.first - b.first;
    int dy = a.second - b.second;

    return dx * dx + dy * dy;
}

pos swapXY(const pos &a)
{
    return {a.second, a.first};
}

int getMinDistSq()
{
    sort(posArr, posArr + n);

    set<pos> s;
    s.insert(swapXY(posArr[0]));
    s.insert(swapXY(posArr[1]));

    int minDistSq = calcDistSq(posArr[0], posArr[1]);
    int startIndex = 0;

    for (int index = 2; index < n; ++index)
    {
        const pos &curPos = posArr[index];

        while (startIndex < index)
        {
            const pos &startPos = posArr[startIndex];
            int dx = startPos.first - curPos.first;

            if (dx * dx < minDistSq)
            {
                break;
            }
            else
            {
                s.erase(swapXY(startPos));
                ++startIndex;
            }
        }

        int minDist = sqrt(minDistSq);

        auto lb = s.lower_bound({curPos.second - minDist, -10000});
        auto ub = s.upper_bound({curPos.second + minDist, 10000});

        while (lb != ub)
        {
            minDistSq = min(minDistSq, calcDistSq(curPos, swapXY(*lb)));
            ++lb;
        }

        s.insert(swapXY(curPos));
    }

    return minDistSq;
}

int main()
{
    input();
    cout << getMinDistSq();
    return 0;
}

풀이

x로 정렬된 기준, y로 정렬된 기준이 하나씩 필요합니다.
y로 정렬된 기준은 set을 활용해서 관리해 주면 됩니다.

x를 기준으로 정렬한 뒤 가장 앞에 2개의 수로 짧은 거리의 기준을 정합니다.
이후 3번째부터 차례대로 확인해 보는데 만약 현재 점을 기준으로 짧은 거리 내에 없다면 y로 정렬된 기준에서도 제거해 줍니다.

이후 set내에서 짧은 거리 내에 존재하는 점들을 추출해낸 뒤 짧은 거리를 갱신해 주면 됩니다.
처음 풀 때는 제곱근 한 값에 소수점을 고려하여 1을 더했었는데 어차피 짧은 거리를 갱신하려는 것이기에 1을 더하는 것은 오히려 비효율적입니다.