일반 convex_hull과 다르게 greedy_convex_hull을 정의했습니다. greedy는 ccw(base, p1, p2) == 0일 때, base에서 먼 것을 작은 것으로 취급하여 정렬합니다. 이러면 마지막 점들 중 ccw(base, p1, p2) == 0인 점들은 먼 것부터 작은 것으로 순열에 넣으면 됩니다. 두 번 째 점부터 탐색해서 ccw(base, p1, p2) == 0이 아닐 때까지 탐색하고 그 것들을 담은 stack을 뒤집어서 순열에 넣어주면 됩니다.
문제를 재귀적으로 이해했는데, 초기에 ccw로 한 번 도형을 돌고 나서 남은 점들과 stack에 추가된 점들 중 마지막 두 점들을(base점과 일직선이 아닐 때까지 밀어줍니다.) 합친 새로운 coordinates들로 재귀를 돕니다. 이 때 base는 마지막 두 점(last, second) 중 second를 택합니다.
재귀 함수에서는 cw로 한 번 돌고 rem이 비었다면 ccw로 한 번 돌고 그래도 rem이 비었다면 재귀를 또 도는 식입니다.
순열에 집어넣는 순서를 잘 짜야됩니다.
홀짝을 반복하는 듯한 재귀 말고도 정렬 한 방에 풀 수도 있는 것 같고 그 풀이가 정석인 것 같네요.
juyoung35 3년 전
일반 convex_hull과 다르게 greedy_convex_hull을 정의했습니다. greedy는 ccw(base, p1, p2) == 0일 때, base에서 먼 것을 작은 것으로 취급하여 정렬합니다. 이러면 마지막 점들 중 ccw(base, p1, p2) == 0인 점들은 먼 것부터 작은 것으로 순열에 넣으면 됩니다. 두 번 째 점부터 탐색해서 ccw(base, p1, p2) == 0이 아닐 때까지 탐색하고 그 것들을 담은 stack을 뒤집어서 순열에 넣어주면 됩니다.
문제를 재귀적으로 이해했는데, 초기에 ccw로 한 번 도형을 돌고 나서 남은 점들과 stack에 추가된 점들 중 마지막 두 점들을(base점과 일직선이 아닐 때까지 밀어줍니다.) 합친 새로운 coordinates들로 재귀를 돕니다. 이 때 base는 마지막 두 점(last, second) 중 second를 택합니다.
재귀 함수에서는 cw로 한 번 돌고 rem이 비었다면 ccw로 한 번 돌고 그래도 rem이 비었다면 재귀를 또 도는 식입니다.
순열에 집어넣는 순서를 잘 짜야됩니다.
홀짝을 반복하는 듯한 재귀 말고도 정렬 한 방에 풀 수도 있는 것 같고 그 풀이가 정석인 것 같네요.