4181번 - Convex Hull
간단한 ccw 문제인 줄 알았는데, 아닌가보네요
우선 'Y'인 것들은 탐색 대상에 속하게 했으며, ccw를 이용해 반시계 방향으로 확실하게 정렬해줬다고 생각했는데 25%에서 틀리네요.
60 0 Y1 -1 Y2 -2 Y4 -1 Y5 0 Y3 1 Y
같은 반례 때문에 직선상에서의 예외처리를 거리를 따져서 해봤는데,
어디가 문제인걸까요?
단순 정렬이 아니라 Graham scan 이라는 CH를 구하는 알고리즘을 사용하셔야 합니다.
반례 드리겠습니다.120 0 Y0 1 Y0 2 Y0 3 Y1 3 Y2 3 Y3 3 Y3 2 Y3 1 Y3 0 Y2 0 Y1 0 Y
@djs100201
반례가 큰 도움이 되었습니다. 정말 감사합니다.
댓글을 작성하려면 로그인해야 합니다.
kth990303 3년 전 1
간단한 ccw 문제인 줄 알았는데, 아닌가보네요
우선 'Y'인 것들은 탐색 대상에 속하게 했으며, ccw를 이용해 반시계 방향으로 확실하게 정렬해줬다고 생각했는데 25%에서 틀리네요.
6
0 0 Y
1 -1 Y
2 -2 Y
4 -1 Y
5 0 Y
3 1 Y
같은 반례 때문에 직선상에서의 예외처리를 거리를 따져서 해봤는데,
어디가 문제인걸까요?