볼록 껍질

다각형의 임의의 두 꼭짓점을 잇는 선분이 항상 그 다각형의 내부에 포함되면 그 다각형을 볼록 다각형이라고 한다. 이 문제에서는 모든 내각이 180도 미만인 다각형만 볼록 다각형으로 본다.

2차원 평면에 서로 다른 점 N개가 주어진다. 이 점들 중 일부를 꼭짓점으로 골라 모든 점을 내부 또는 경계에 포함하는 가장 바깥쪽 볼록 다각형을 만들 수 있다. 이 다각형을 주어진 점 집합의 볼록 껍질이라고 한다.

주어진 점들로 이루어지는 볼록 껍질의 꼭짓점 개수를 구하는 프로그램을 작성하시오.

첫째 줄에 점의 개수 N이 주어진다. (3 <= N <= 100,000)

둘째 줄부터 N개의 줄에 걸쳐 각 점의 x좌표와 y좌표가 공백으로 구분되어 주어진다. 모든 점의 좌표는 서로 다르며, 각 좌표의 절댓값은 40,000을 넘지 않는다.

입력으로 주어지는 모든 점이 한 직선 위에 있는 경우는 없다.

첫째 줄에 볼록 껍질을 이루는 점의 개수를 출력한다.

볼록 껍질의 한 변 위에 여러 점이 놓여 있으면, 그 변의 양 끝점만 개수에 포함한다.