009 - 天空の城ツルガ
時間制限 5 秒 / メモリ制限 256 MB / 得点 11 / x 0 /
問題文
天空の城ツルガはアイヅ国の上空に浮かんでいる。アイヅ国では、天空の城ツルガによって日光がさえぎられる日もある。日光が当たらない日があった場所の住人には、その日数に応じて補償金を支払っている。アイヅ国の補償金支払い担当者であるあなたは、天空の城ツルガの日ごとの位置と補償金の申請があった場所のリストから、その日にその場所で日光が当たらなかったことを確かめる必要がある。
天空の城ツルガの場所とアイヅ国の地上のある場所が与えられたとき、その日にその場所が影に入っていたかどうかを判定するプログラムを作成せよ。影の中に入っていたかどうかは、ある特定の時刻で判定するので、天空の城ツルガや太陽の移動については考えなくて良い。太陽の位置は$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$
1行目に天空の城ツルガの領域を表す点の数$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より大きいと考えて良い。続く1行に、補償金の申請があった場所の数$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」を1行に出力する。
入出力例
入力例1
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
1 0 1 0 0
入力例2
4 100000 100000 101000 100000 101000 101000 100000 101000 2 100005 100005 101005 101005
出力例2
0 1