시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 2023 490 243 20.593%

문제

다각형의 임의의 두 꼭지점을 연결하는 선분이 항상 다각형 내부의 존재하는 다각형을 볼록 다각형이라고 한다. 아래 그림에서 (a)는 볼록 다각형이며, (b)는 볼록 다각형이 아니다.

조금만 생각해 보면 다각형의 모든 내각이 180도 이하일 때 볼록 다각형이 된다는 것을 알 수 있다. 편의상 이 문제에서는 180도 미만인 경우만을 볼록 다각형으로 한정하도록 한다.

2차원 평면에 N개의 점이 주어졌을 때, 이들 중 몇 개의 점을 골라 볼록 다각형을 만드는데, 나머지 모든 점을 내부에 포함하도록 할 수 있다. 이를 볼록 껍질 (CONVEX HULL) 이라 한다. 아래 그림은 N=10인 경우의 한 예이다.

점의 집합이 주어졌을 때, 볼록 껍질을 이루는 점의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 점의 개수 N(3≤N≤100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 점의 x좌표와 y좌표가 빈 칸을 사이에 두고 주어진다. 주어지는 모든 점의 좌표는 다르다고 가정해도 좋다. x좌표와 y좌표의 범위는 절대값 40,000을 넘지 않는다.

출력

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

예제 입력

8
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2

예제 출력

5

힌트

출처

  • 문제를 만든 사람: author5
  • 잘못된 데이터를 찾은 사람: myungwoo