Convex Hull

Convex Hull(볼록 껍질)은 주어진 모든 점을 포함하는 가장 작은 볼록다각형이다.

Graham Scan

https://www.crocus.co.kr/1288

1. 기준점을 잡는다. (보통 y좌표가 가장 작은 점을 기준으로 한다)
2. 기준점으로 하여 다른 점들을 반시계 방향으로 정렬한다.
3. 첫 번째와 두 번째 정점을 스택에 넣고 시작한다.
4. 스택에서 second와 first를 순서대로 꺼내고 next값과 ccw를 하여 > 0인지 확인한다. (좌회전 하는지 확인)
5. 좌회전한다면 볼록 껍질이 될 수 있다는 의미이고 pop했던 second를 다시 스택에 넣어 주고 next도 스택에 넣어 준다.
6. 우회전한다면 second 점은 버리고 first를 스택에 넣는다.
7. 4번 과정을 next값이 없을 때까지 반복한다.

스택에 남아 있는 점들이 Convex Hull이다.