[Python] 백준 10254 - 고속도로

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

문제

n개의 도시를 가진 나라가 있다. 이 나라에서는 도시들 중 가장 먼 두 도시 사이에 직행 고속도로를 놓으려 한다.

고속도로는 시작점과 끝점이 아닌 다른 나라를 통과해도 된다. 즉, n개의 도시 중 유클리드 거리가 가장 먼 두 도시를 찾으려 한다. 모든 도시는 한 평면 위에 있다.

위의 예제에서는 (12,0)의 도시와 (-6,3)의 도시가 가장 먼 유클리드 거리를 갖는다.

도시 n개의 좌표가 주어지면 모든 두 도시 쌍의 거리 중 가장 먼 두 도시를 찾아라.

입력

첫째 줄에 테스트 케이스의 수 T가 주어진다. 

각 테스트 케이스의 첫 줄엔 도시의 개수 n이 주어진다. (2 ≤ n ≤ 200,000) 그 후 n줄에 걸쳐 각 도시의 x좌표와 y좌표가 주어진다. (-10,000,000 ≤ x, y ≤ 10,000,000) x, y는 항상 정수이며, 어떤 두 도시가 같은 점 위에 있는 경우는 없다.

출력

테스트 케이스마다 가장 먼 두 점의 좌표를 출력한다.

만일 그 두 점의 좌표가 각각 (x1, y1), (x2, y2)이라면 x1 y1 x2 y2를 출력하면 된다.

가장 먼 거리를 갖는 두 점의 쌍이 여러 개라면 그 중 아무 것이나 출력해도 상관없다.

 

---

 

풀이

단계별로 풀어보기에서 컨벡스 헐 관련 문제를 풀다가 컨벡스 헐 응용문제라길래 한 번 도전해봤는데...

젠장. 이 문제는 회전하는 캘리퍼스라는 알고리즘을 알아야 한다.

그래서 그냥 회전하는 캘리퍼스에 대해서 배워보도록 하자.

 

일단 가장 먼 두 점 사이의 거리를 구하는 것(또는 그 두 점)이 회전하는 캘리퍼스 알고리즘에서 구하는 것이다.

자명하게도, 그 두 점은 컨벡스 헐 위에 있을 것이다.

 

컨벡스 헐의 점들을 구할때는 시계방향이든 반시계방향이든 정렬이 되어있어야 한다. 그래햄 스캔 알고리즘을 쓸 수도 있겠지만 이전 글에서 배운 앤드류 알고리즘을 이용하면 쉽게 시계방향으로 정렬을 할 수 있다.

 

컨벡스 헐 위의 모든 두 점 쌍에 대해서 조사를 진행할 수 있을 것이다. 다만, 이러면 시간복잡도는 O(n^2)가 나오게 된다.

 

그러면 이제 회전하는 캘리퍼스 알고리즘이 어떻게 작동하는지 알아보도록 하자.

 

---

1. 한 점을 임의로 잡는다. 그리고 그 다음 점과 연결한 벡터를 얻는다. 이 벡터를 A라고 하자.

2. 처음의 잡은 한 점의 다음 점과 다음다음점을 연결한 벡터로 처음에는 시작한다. 이 벡터는 B라고 하자.

3. B벡터의 끝점이 시계방향으로 회전한다고 가정한다. AxB(외적)의 값이 시계방향일때는 쭉 진행하고, 중간에 0 또는 반시계방향으로 바뀌었다면 그 점과 거리를 재고 리스트에 추가하고, A벡터의 시작점을 한 칸 앞으로 옮긴다.

4. A벡터의 시작점이 처음으로 돌아올 때까지 3을 반복한다.(한 바퀴 돌 때까지)

5. 리스트에 있는 거리들 중 최대가 정답이다.

---

증명은 다른 블로그들을 찾아보길 바란다.

 

간단한 예시를 그림으로 들어보면 다음과 같다.

 

 

구현의 경우, 살짝 헷갈리고 복잡하기는 하나 그래도 차근차근히 하면 할 수는 있다.

벡터 외적을 할 때 헷갈리지 않게 평행이동을 잘 해주는 것이 중요하다.

def dist(d1, d2):
    x1, y1 = d1
    x2, y2 = d2
    return (x1-x2)**2 + (y1-y2)**2

def CCW(d1, d2, d3): #d1, d2, d3은 튜플임
    x1, y1 = d1
    x2, y2 = d2
    x3, y3 = d3
    return (x2-x1)*(y3-y2) - (x3-x2)*(y2-y1)

def hull(dots):
    #Top Hull
    dots.sort()
    top = []
    for d in dots:
        while len(top) >= 2 and CCW(top[-2], top[-1], d) >= 0:
            top.pop()
        top.append(d)

    #Bottom Hull
    dots = dots[::-1]
    bottom = []
    for d in dots:
        while len(bottom) >= 2 and CCW(bottom[-2], bottom[-1], d) >= 0:
            bottom.pop()
        bottom.append(d)

    top.pop()
    bottom.pop()
    return top + bottom


T = int(input())
for _ in range(T):
    dots = []
    n = int(input())
    for i in range(n):
        x, y = map(int, input().split())
        dots.append((x, y))
    h = hull(dots)
    N = len(h)
    ans = []
    firstidx = 0
    secondidx = 1
    while firstidx < N:
        firststart = h[firstidx]
        firstend = h[(firstidx+1)%N]
        secondstart = h[secondidx % N]
        secondend = h[(secondidx + 1) % N]
        secondend = (secondend[0] - secondstart[0] + firstend[0], secondend[1] - secondstart[1] + firstend[1])
        while CCW(firststart, firstend, secondend) < 0:
            secondidx += 1
            secondstart = h[secondidx % N]
            secondend = h[(secondidx + 1) % N]
            secondend = (secondend[0] - secondstart[0] + firstend[0], secondend[1] - secondstart[1] + firstend[1])
        ans.append((dist(firststart, secondstart), firststart, secondstart))
        firstidx += 1
    tmp = max(ans)
    print(*tmp[1], *tmp[2])

 

오늘은 회전하는 캘리퍼스 알고리즘을 이용하여 문제를 풀어보았다. 이 알고리즘으로 O(n)의 시간복잡도 안에 두 점 사이 거리의 최댓값을 구할 수 있다!!(물론 컨벡스 헐 구하려면 nlogn이 걸리긴 함)