삼각형
시간 제한2초메모리 제한512 MB
세 점의 시계 방향 여부만 묻는 질의를 제한 횟수 안에서 사용해 n개 점의 볼록 껍질 꼭짓점 개수를 구한다.
문제
바이트랜드는 n (n ≥ 3)개의 도시가 있는 나라이고, 도시들은 2차원 평면 위의 서로 다른 n개의 점으로 나타낼 수 있다. 도시에는 1번부터 n번까지 번호가 붙어 있다. 관광객인 당신은 바이트랜드 도시들의 정확한 위치를 모른다. 관광 잡지에서 세 도시가 한 직선 위에 있는 경우는 없다는 사실만 알아냈다.
n개의 점 집합의 볼록 껍질은 n개의 점이 모두 내부나 경계에 있는 가장 넓이가 작은 볼록 다각형이다. 볼록 다각형은 모든 내각이 180도보다 작고 스스로 교차하지 않는다.
바이트랜드 도시 집합의 볼록 껍질 경계 위에 있는 꼭짓점의 개수를 구해야 한다. 서로 다른 세 도시 번호 i, j, k (1 ≤ i, j, k ≤ n)에 대한 질문만 할 수 있다. 이런 질문은 도시 i, j, k를 꼭짓점으로 하는 삼각형에 대한 것이다. 질문의 답은 삼각형의 꼭짓점을 i, j, k 순서로 지날 때 시계 방향인지 반시계 방향인지를 나타낸다.
제한
- 3 ≤ n ≤ 40 000.
- is_clockwise는 최대 1 000 000번 호출할 수 있다.