programmer life guidance 101

www.acmicpc.net/problem/1708 1708번: 볼록 껍질 첫째 줄에 점의 개수 N(3 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 점의 x좌표와 y좌표가 빈 칸을 사이에 두고 주어진다. 주어지는 모든 점의 좌표는 다르다고 가정해도 좋다. x�� www.acmicpc.net 문제 다각형의 임의의 두 꼭짓점을 연결하는 선분이 항상 다각형 내부에 존재하는 다각형을 볼록 다각형이라고 한다. 아래 그림에서 (a)는 볼록 다각형이며, (b)는 볼록 다각형이 아니다. 조금만 생각해 보면 다각형의 모든 내각이 180도 이하일 때 볼록 다각형이 된다는 것을 알 수 있다. 편의상 이 문제에서는 180도 미만인 경우만을 볼록 다각형으로 한정하도록 한다. 2차원 평면에 N개의 점..

> Convex Hull(볼록 껍질) 볼록 껍질(convex hull)이라는 개념은 2차원 평면상에 점이 여러 개가 있을 때 이 점들 중 일부를 골라서 만들 수 있는, 나머지 점들을 모두 포함하는 볼록다각형을 말합니다. 이때 포함한다는 말은 점이 다각형의 경계에 걸쳐 있는 것도 인정합니다. 즉, 변 위에 있어도 된다는 것. 이런 점들이 있다면, 이것이 바로 볼록 껍질입니다. 볼록 껍질에 속한 점 개수는 6개군요. 그럼 이러한 다각형이 왜 항상 볼록다각형으로 결정될 수 있을까요? 사실 그건 조금만 생각해 보면 직관적으로 당연합니다. 점을 모두 포함하는 어떤 오목다각형이 있다고 해도, 오목한 지점의 점을 다각형에서 제외시키고 전후의 점을 그냥 이어버려도 새 다각형에 그 점도 포함이 되니까요. 또한, 볼록다각..