009 - 天空の城ツルガ

問題文

天空の城ツルガはアイヅ国の上空に浮かんでいる。アイヅ国では、天空の城ツルガによって日光がさえぎられる日もある。日光が当たらない日があった場所の住人には、その日数に応じて補償金を支払っている。アイヅ国の補償金支払い担当者であるあなたは、天空の城ツルガの日ごとの位置と補償金の申請があった場所のリストから、その日にその場所で日光が当たらなかったことを確かめる必要がある。

天空の城ツルガの場所とアイヅ国の地上のある場所が与えられたとき、その日にその場所が影に入っていたかどうかを判定するプログラムを作成せよ。影の中に入っていたかどうかは、ある特定の時刻で判定するので、天空の城ツルガや太陽の移動については考えなくて良い。太陽の位置は$x=y=0,z=10^6$にある大きさのない点であり、天空の城ツルガは$z=100$の平面にある凸多角形、地上の場所は$z=0$にある大きさのない点とする。また、ある地点と太陽を結ぶ直線を天空の城ツルガがさえぎるとき、その地点は影に入るものとする。

入力

入力は以下の形式で与えられる。

$N$
$xt_1$ $yt_1$
$xt_2$ $yt_2$
:
$xt_N$ $yt_N$
$Q$
$xa_1$ $ya_1$
$xa_2$ $ya_2$
:
$xa_Q$ $ya_Q$

１行目に天空の城ツルガの領域を表す点の数$N$ ($3 \leq N \leq 3 \times 10^4$)が与えられる。続く$N$行に、領域を構成する頂点の座標$xt_i$,$yt_i$ ($-10^8 \leq xt_i,yt_i \leq 10^8$)が領域の重心の周りに反時計回りに整数で与えられる。ただし、同じ座標をもつ頂点は与えられない（$i \ne j$について、$xt_i \ne xt_j$ または $yt_i \ne yt_j$）。また、領域の面積は0より大きいと考えて良い。続く１行に、補償金の申請があった場所の数$Q$ ($1 \leq Q \leq 6 \times 10^4$)が与えられる。続く$Q$行に、補償金の申請があった場所の座標$xa_i$,$ya_i$ ($-10^8 \leq xa_i,ya_i \leq 10^8$)が整数で与えられる。ただし、補償金の申請があった場所の座標は、天空の城ツルガの影の輪郭線から距離$10^{-3}$以上離れていると考えて良い。

出力

補償金の申請があった各場所について、影に入っていたら「1」、入っていなかったら「0」を１行に出力する。

入出力例

入力例１

6
0 0
4 0
6 3
5 5
1 5
0 3
5
2 2
6 6
3 1
5 1
-1 -1

出力例１

1
0
1
0
0

入力例２

4
100000 100000
101000 100000
101000 101000
100000 101000
2
100005 100005
101005 101005

出力例２

0
1