SOJ ONLINE JUDGE

볼록 다각형 내부의 점 판정

난이도: Platinum III 출제자: rlatjwls7882 시간 제한: 1000 ms 메모리 제한: 512 MB
기하학볼록 껍질볼록 다각형 내부의 점 판정

$N$개의 꼭짓점으로 이루어진 볼록 다각형이 있다. $Q$개의 점에 대해 각 점이 볼록 다각형의 내부에 있는지 판별하라.

경계 위에 있는 점은 내부에 있는 것으로 보지 않는다.

입력

첫 번째 줄에 볼록 다각형의 꼭짓점 개수 $N$과 점의 개수 $Q$가 주어진다. $(3 \leq N \leq 200\,000,\ 1 \leq Q \leq 200\,000)$

두 번째 줄부터 $N$개의 줄에 걸쳐 볼록 다각형의 꼭짓점 좌표 $x$, $y$가 반시계 방향으로 주어진다. $(-10^9 \leq x,y \leq 10^9)$

그 다음 줄부터 $Q$개의 줄에 걸쳐 판별할 점의 좌표 $x$, $y$가 주어진다. $(-10^9 \leq x,y \leq 10^9)$

주어지는 다각형의 넓이는 양수이다.

출력

각 점마다 볼록 다각형의 내부에 있으면 Yes를, 그렇지 않으면 No를 한 줄에 하나씩 출력한다.

예제 입력 1

4 5
0 0
4 0
4 4
0 4
2 2
4 2
5 5
0 0
-1 2

예제 출력 1

Yes
No
No
No
No

제출