kth990303   2달 전

간단한 ccw 문제인 줄 알았는데, 아닌가보네요

우선 'Y'인 것들은 탐색 대상에 속하게 했으며, ccw를 이용해 반시계 방향으로 확실하게 정렬해줬다고 생각했는데 25%에서 틀리네요.

6
0 0 Y
1 -1 Y
2 -2 Y
4 -1 Y
5 0 Y
3 1 Y

같은 반례 때문에 직선상에서의 예외처리를 거리를 따져서 해봤는데,

어디가 문제인걸까요?

djs100201   2달 전

단순 정렬이 아니라 Graham scan 이라는 CH를 구하는 알고리즘을 사용하셔야 합니다.

반례 드리겠습니다.
12
0 0 Y
0 1 Y
0 2 Y
0 3 Y
1 3 Y
2 3 Y
3 3 Y
3 2 Y
3 1 Y
3 0 Y
2 0 Y
1 0 Y

kth990303   2달 전

@djs100201

반례가 큰 도움이 되었습니다. 정말 감사합니다.

댓글을 작성하려면 로그인해야 합니다.