[Python] 5746번 Onion Layers

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

---

 

25/08/28

 

 

쉬운 볼록껍질 문제다. Do You know Convex Hull??

---

 

문제 접근 방식:

 

 

볼록껍질 구하고 해당 볼록껍질에 속한 점은 기존 점 리스트에서 날린다.

 

이걸 반복하면서 볼록 껍질 개수를 세준다. 짝수 개면 안된다고 하고, 홀수 개면 OK란다.

 

약간의 예외처리 사항은 점이 2개 이하일 때는 볼록 껍질을 만들 수 없다는 점과, 180도일 때 여러 점을 포함하지 않고 끝 점만 포함한다는 점이다.

 

해당 부분을 틀려서 2번 틀렸다.

 

볼록껍질 코드는 모노톤 체인으로 구현했다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 5746번 Onion Layers
# 기하학, 볼록껍질
import sys
# [-] Direction vector from p1 to p2
def dirvec(p1, p2):
    return (p2[0]-p1[0], p2[1]-p1[1])
# [-] Cross product
def crossproduct(p1, p2):
    return p1[0]*p2[1] - p2[0]*p1[1]
# [-] CCW
def ccw(p1, p2, p3):
    vec1, vec2 = dirvec(p1, p2), dirvec(p2, p3)
    CCW = crossproduct(vec1, vec2)
    if CCW < 0: return -1
    elif CCW == 0: return 0
    else: return 1
# [-] ConvexHull with monotone chain
def convexhull(point_li):
    point_li.sort()
    # [-] There is no convex hull if #(points) < 3
    if len(point_li) < 3:
        return []
    # [-] Construct upper hull
    upper_hull = []
    upper_hull.append(point_li[0]); upper_hull.append(point_li[1])
    for i in range(2, len(point_li)):
        p = point_li[i]
        while len(upper_hull) >= 2 and ccw(upper_hull[-2], upper_hull[-1], p) > 0:
            upper_hull.pop()
        upper_hull.append(p)
    # [-] Construct lower hull
    lower_hull = []
    lower_hull.append(point_li[0]); lower_hull.append(point_li[1])
    for i in range(2, len(point_li)):
        p = point_li[i]
        while len(lower_hull) >= 2 and ccw(lower_hull[-2], lower_hull[-1], p) < 0:
            lower_hull.pop()
        lower_hull.append(p)
    # [-] Merging upper hull and lower hull
    hull = lower_hull + upper_hull[-2:0:-1]
    return hull

def solve(point_li):
    hull_num = 0
    while point_li:
        hull = convexhull(point_li)
        if hull == []: break
        point_set = set(point_li) - set(hull)
        point_li = list(point_set)
        hull_num += 1
    if hull_num % 2 == 0:
        print('Do not take this onion to the lab!')
    else:
        print('Take this onion to the lab!')
    return

def main():
    while True:
        N = int(input())
        if N == 0:
            return
        point_li = [tuple(map(int, input().split())) for _ in range(N)]
        solve(point_li)

main()