[BOJ 4181]

문제 바로가기 : https://www.acmicpc.net/problem/4181
문제 설명은 위 링크에서 확인해주시길 바랍니다.

solution

review

BOJ 3679: 단순다각형과 거의 동일한 문제다. 정렬 하나만 바꿔주면 된다.
input에서 Y인 점은 볼록 껍질에 반드시 포함이 돼야 하며, N인 점은 포함하지 않아도 된다.
근데 Y인 점 중에서 일직선 상에 있거나 ccw>0 이 아닌 점은 일반적인 convex hull 알고리즘에서는 포함되지 않을 수 있다.
하지만 여기서는 Y인 점을 반드시 포함해야 한다.

점을 생략하지 않기 위해서 문제에서 정해준 조건에 맞춰 정렬을 수행한다.
그리고 첫 번째 점과 일직선을 이루는 점들은 거리가 먼 순서로 정렬해주자.