[백준/C,C++] 2261번: 가장 가까운 두 점

www.acmicpc.net/problem/2261

2261번: 가장 가까운 두 점

www.acmicpc.net/problem/6549

6549번: 히스토그램에서 가장 큰 직사각형

개인적으로 문제를 처음 봤을 땐 6549번: 히스토그램에서 가장 큰 직사각형 문제와 비슷하다 느꼈습니다.

 

그런데 영역을 좌, 우로 나누고 값을 반환한 뒤 좌, 우 모두에 포함되어있는 값을 찾고자 할 때,

 

6549번 문제 같은 경우 가장 높은 쪽으로 먼저 탐색하는 것이 최선의 방법이라

 

단 한 번의 반복문만으로도 모두 탐색이 가능했습니다.

 

 

좌표평면에 8개의 점이 있다고 생각해 봅시다.

 

여기서 왼쪽의 경우에는 초록색 점들이 가장 가까운 두 점일 것이고,

 

오른쪽의 경우에는 파란색 점들이 가장 가까운 두 점일 것입니다.

 

그리고 8개의 점을 고려해야 하는 단계에서 분할된 좌, 우의 영역에서 가장 가까운 두 점을 찾은 것은

 

현재 단계에서 가장 가까운 두 점을 찾는 것과 큰 관계가 없어 보입니다.

 

왜냐하면 두 영역에서 고려되지 않은 두 점 사이의 거리들을 전부 다시 재봐야 하기 때문이죠.

 

하지만 실제로 현재 갱신되어있는 가장 가까운 두 점보다

 

거리가 가까운 두 점은 빨간 선으로 테두리 쳐진 영역 안에 존재할 수밖에 없습니다.

 

왼쪽 영역에 선과 가장 밀접하게 붙어있는 점이 있다고 생각해봅시다.

 

이 점과 거리를 잴 오른쪽 영역의 점이 테두리 밖에 있다면 이미 최소 거리보다 큰 값이 되므로

 

고려해볼 필요가 없습니다.

 

y축을 기준으로도 마찬가지입니다.

 

위 그림에서 작은 빨간 테두리 안 파란색 점과 비교 대상이 될 점은 검은 점 하나뿐입니다.

 

이렇게 모든 경우의 수 중 이미 x축과 y축의 차이가 최소 거리보다 크다면 가지치기를 하며 탐색을 하면 됩니다.

 

int dis(const p& p1, const p& p2)
{
    int x = p1.X - p2.X;
    int y = p1.Y - p2.Y;
    return power(x) + power(y);
}

 

거리를 재는 함수입니다.

 

실제로 두 점 간의 거리는 $\sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}$ 이지만,

 

편의를 위해 루트를 제거한 값만으로 비교하겠습니다.

 

int closest(int l, int r)
{
    int n = r - l + 1;
    if (n == 2) return dis(ps[l], ps[r]);
    if (n == 3) {
        return min({ dis(ps[l], ps[l + 1]), dis(ps[l + 1], ps[l + 2]), dis(ps[l], ps[r]) });
    }

    int mid = (l + r) / 2;
    int ret = min(closest(l, mid), closest(mid + 1, r));

    vector<p> in;
    in.reserve(n);
    int line = (ps[mid].X + ps[mid + 1].X) / 2;

    for (int i = l; i < r; i++) {
        if (power(line - ps[i].X) < ret) {
            in.push_back(ps[i]);
        }
    }

    sort(in.begin(), in.end(), cmp);

    int len = in.size();
    for (int i = 0; i < len; i++) {
        for (int j = i + 1; j < len; j++) {
            if (power(in[i].Y - in[j].Y) >= ret) break;
            else ret = min(ret, dis(in[i], in[j]));
        }
    }

    return ret;
}

 

점이 담긴 pair<int, int> 배열의 값 중 l~r 인덱스 사이의 가장 짧은 두 점 간의 거리를 반환하는 closest 함수입니다.

 

중요한 점이 있는데 해당 함수를 실행 시키기 전 점들을 입력받고 x좌표 순으로 정렬해야 한다는 점입니다.

 

비교할 점의 개수가 2~3개인 경우는 기저 사례로 바로 최소 거리를 반환합니다.

 

처음 ret 의 값은 좌, 우 영역 중 가장 가까운 두 점 사이의 거리가 반환되며

 

이후 중심선(line)을 기준으로 line - 최소거리 ~ line + 최소거리에 해당하는 점들만 벡터에 push해줍니다.

 

y좌표 순으로 정렬한 뒤, 해당 점과 비교할 점의 y축 차이가 최소거리를 벗어날 때까지만 탐색하여

 

해당 단계에서 제일 가까운 두 점을 자신을 호출한 곳으로 반환하게 됩니다.