32118번 - 감옥

문제

무한한 영역이 감옥이기 때문에 절대로 탈옥할 수 없어 악명 높은 좌표평면 감옥에 $Q$명의 죄수가 갇혀 있다.

감옥을 감시하는 교도관은 원점에 서 있으며, 죄수들을 볼 수 있는 시야가 있다. 교도관의 시야는 다음 조건을 만족함이 알려져 있다.

• 교도관의 시야는 꼭짓점이 $N$개인 단순다각형으로 둘러싸여 있으며, 단순다각형의 선분을 포함한 내부는 시야 내부, 선분을 제외한 외부는 시야 외부이다.
• 교도관이 특정 지점을 볼 수 있다면, 그 방향으로 그보다 더 가까운 곳도 볼 수 있다. 엄밀히 말해, 시야 내부의 임의의 점과 원점을 잇는 선분 위의 모든 점은 시야 내부에 있다.
• 원점 주변은 교도관이 언제나 볼 수 있다. 엄밀히 말해, 원점을 중심으로 하고 반지름이 $\varepsilon$인 원이 교도관의 시야 내부에 포함되는 $\varepsilon >0$이 존재한다.

이 감옥에 갇힌 $Q$명의 죄수들이, 조금의 자유라도 쟁취하기 위해 힘을 모아 교도관의 시야에서 벗어나기 위해 시도하고 있다. 시야를 더욱 효과적으로 벗어나기 위해, 모든 2ドル\leq i\leq Q$에 대해 $i$번 죄수가 $(i-1)$번 죄수가 시야 내에 있는지 여부에 따라 다음과 같이 순서대로 움직인다.

• $(i-1)$번 죄수가 이동한 후 시야 내부에 있었다면, $i$번 죄수는 $(i-1)$번 죄수가 있는 방향의 반대 방향을 본 뒤 둘 사이의 거리만큼 이동한다.
• $(i-1)$번 죄수가 이동한 후 시야 외부에 있었다면, $i$번 죄수는 $(i-1)$번 죄수가 있는 방향을 바라본 뒤, 둘 사이 거리의 절반만큼 이동한다. 단, 정수 격자점이 아닌 점은 오래 있기 불편하게 설계되었으므로, 이동한 후 가장 가까운 정수 격자점 중 원점과 가장 가까운 점으로 이동한다.

자유를 중시하는 당신이 교도관의 시야 정보를 소식통으로부터 입수했고, 이를 이용해서 죄수들에게 시야 안에 있는지 밖에 있는지를 알려주고자 한다. 현재 죄수들의 위치가 주어지면, 이동 후 각 죄수가 시야 내부에 있는지 외부에 있는지를 판별하는 프로그램을 작성하여라.

입력

첫 줄에 $N$과 $Q$가 공백을 사이에 두고 주어진다. (3ドル\leq N\leq 100,000円$; 1ドル\leq Q\leq 100,000円$)

둘째 줄부터 $N$개의 줄에 걸쳐 시야를 나타내는 단순다각형의 정보가 주어진다. 모든 1ドル \leq i \leq N$에 대해, $(i+1)$번째 줄에는 $x_{i}$와 $y_{i}$가 공백을 사이에 두고 주어진다. ($-1,000円,000円\leq x_i,y_i\leq 1,000円,000円$) 이는 다각형의 반시계방향으로 $i$번째 점이 $(x_i,y_i)$라는 의미이다.

$(N+2)$번째 줄부터 $Q$개의 줄에 걸쳐 각 죄수의 정보가 주어진다. 모든 1ドル \leq j \leq Q$에 대해 $(N+j+1)$번째 줄에는 $u_{j}$와 $v_{j}$가 공백을 사이에 두고 주어진다. ($-1,000円,000円\leq u_j,v_j\leq 1,000円,000円$) 이는 $j$번 죄수의 처음 위치가 $(u_j,v_j)$라는 의미이다.

주어지는 모든 좌표는 정수이며, 주어지는 다각형은 문제에서 설명하는 시야 조건을 만족한다. 주어지는 다각형의 연속한 세 점은 한 직선 위에 있지 않다.

출력

총 $Q$개의 줄을 출력한다. 모든 1ドル \leq i \leq Q$에 대해, $i$번째 줄에는 $i$번째 죄수가 시야 내부에 있다면 1, 아니면 0을 출력한다.

제한

힌트