[Python] 백준 9892 - Width

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

문제(직접 핵심만 번역해보겠음)

2차원 평면 상에 점들이 여러개 주어진다. width w는 이 점들을 모두 감싸는 두 평행한 직선 사이의 최소 거리이다.

예를 들면 다음 그림과 같다.

당신은 주어진 점들에 대해서 w^2를 계산한 다음 이 수의 정수 부분만 출력하면 된다.

 

이 문제를 쉽게 풀게 하기 위해 공식을 하나 제공하겠다. 

삼각형 ABC가 있어서 A(xa, ya), B(xb, yb), C(xc, yc)라고 할 때 이 삼각형의 높이 h는

과 같이 계산될 수 있다. 여기서 문자 시그마의 값은 ABC가 반시계방향이면 1이고 시계방향이면 -1이다. Figure 2를 참고하라.

모든 점들이 일직선에 놓여있다면, width는 0이 된다.

 

입력

첫 번째 줄에는 점의 개수인 n이 주어진다(100000 이하). 다음 n개의 줄에는 각각의 점의 x, y좌표가 빈칸으로 구분되어 주어진다. x, y좌표는 0, 199 사이의 정수이다. 같은 점이 여러 번 입력으로 주어질 수 있다.

출력

w^2의 정수부분을 출력하세요.

 

---

 

풀이

회전하는 캘리퍼스 응용문제를 보던 중 해결한 사람이 1명밖에 없는 다이아 문제를 발견하여 도전하였다.

 

보통 회전하는 캘리퍼스 문제에서는 두 점 사이 거리의 최댓값을 구하는데, 이 문제에서는 독특하게 평행한 두 직선 사이의 거리 최솟값을 구한다.

 

아이디어는, 회전하는 캘리퍼스에서 조금의 응용만 하면 된다.

 

점들이 주어졌을 때, 일단 컨벡스 헐을 구하는 것 까지는 똑같을 것이다.

그런데 점들을 모두 포함하는 두 개의 평행한 직선을 어떻게 구할까?

 

예를들어서 AE가 하나의 선이라고 하자. 그러면 거리가 최소가 되면서 모든 점을 포함하려면 AE를 기준으로 높이가 가장 높은 C 점을 지나게 직선을 잡으면 될 것이다.

 

이 C 점을 잡는 방법에서 회전하는 캘리퍼스를 응용한다. 왜냐? AE벡터를 기준으로 보았을 때 보통의 회전하는 캘리퍼스에서 하듯이 벡터를 옮겨가며 CCW를 구해주면, 최고점인 C점에서 CCW의 부호가 바뀌게 된다.

 

그러니까 평소의 캘리퍼스 코드에서 CCW가 바뀌었을 때, 위에서 주어진 공식을 대입하여 후보 리스트에 width를 계산하여 추가한다.

 

그리고 맨 마지막에, min값을 출력해주면 될 것이다. 별로 어렵지 않은 문제이다!

 

def dist(A, B, C):
    x1, y1 = A
    x2, y2 = B
    x3, y3 = C
    return int(((x1-x3)*(y2-y3) - (x2-x3)*(y1-y3))**2 / ((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


dots = set()
n = int(input())
for i in range(n):
    x, y = map(int, input().split())
    dots.add((x, y))
dots = list(dots)
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, firstend, secondstart))
    firstidx += 1
print(min(ans))

 

 

내가 풀고나서 보니 다이아까지는 아닌 것 같아서(풀 당시 기준 D4였음), 회전하는 캘리퍼스의 응용문제인만큼 P1으로 레이팅해주었다.