4181번 - Convex Hull
<입력>
50 0 Y1 -1 Y2 0 Y2 2 Y1 1 Y
<정답>
50 01 -12 02 21 1
우하단으로 일직선일때는 x가 작은 게 먼저
우상단으로 일직선일때는 x가 큰 게 먼저
50 01 12 22 01 -1
이 맞지 않을까요? 예시하신 정답은 시계방향 같습니다.저는 거리 기준으로(피타고라스) Graham scan의 돌아오는 쪽을 역순으로 탐색해 재정렬하고 있습니다.
————-
맙소사. 기초적 실수를 ㅎㅎ 감사합니다.
댓글을 작성하려면 로그인해야 합니다.
rail 2년 전 1
<입력>
5
0 0 Y
1 -1 Y
2 0 Y
2 2 Y
1 1 Y
<정답>
5
0 0
1 -1
2 0
2 2
1 1
우하단으로 일직선일때는 x가 작은 게 먼저
우상단으로 일직선일때는 x가 큰 게 먼저