충전 권역 판정

문제

도시의 평면 위에 전기차 충전소가 N개 있다. i번째 충전소의 위치는 정수 좌표 (x_i, y_i) 이며, 서로 다른 충전소가 같은 위치에 있을 수도 있다.\n\n모든 충전소를 포함하는 가장 작은 볼록 집합을 충전 권역이라 한다. 충전소가 서로 다른 위치 한 곳뿐이면 권역은 그 점 하나이고, 모든 충전소가 한 직선 위에 있으면 권역은 양 끝 충전소를 잇는 선분이다. 그 외의 경우 권역은 내부가 있는 볼록 다각형이며, 그 경계도 권역에 속한다.\n\n이제 전기차 Q대가 있고, j번째 전기차는 정수 좌표 (a_j, b_j) 에 있다. 각 전기차에 대해 그 위치가 충전 권역에 속하는지, 즉 권역의 내부 또는 경계 위에 있는지를 판정하여라. 속하면 IN, 속하지 않으면 OUT 을 출력한다.

입력

첫째 줄에 N과 Q가 공백으로 구분되어 주어진다. (1 ≤ N, Q ≤ 200,000)\n다음 N개의 줄에 x_i y_i 가 주어진다.\n다음 Q개의 줄에 a_j b_j 가 주어진다.\n모든 좌표는 정수이며 절댓값이 10^6 이하이다.

출력

Q개의 줄에 걸쳐, j번째 전기차에 대해 IN 또는 OUT 을 출력한다.

5 4
0 0
4 0
4 4
0 4
2 2
2 2
4 2
5 5
0 0

IN
IN
OUT
IN

4 4
0 0
2 2
4 4
1 1
3 3
5 5
3 2
0 0

IN
OUT
OUT
IN

2 2
1 1
1 1
1 1
1 2

IN
OUT

출처: Devin.KR 자체 제작