AT_abc211_f [ABC211F] Rectilinear Polygons

[problemUrl]: https://atcoder.jp/contests/abc211/tasks/abc211_f $ xy $ 平面上に $ N $ 個の多角形があります。 これらの多角形は、全ての辺が $ x $ 軸または $ y $ 軸に平行で、全ての角が $ 90 $ 度または $ 270 $ 度で、かつ単純です。 $ i $ 個目の多角形は $ M_i $ 個の頂点からなり、$ j $ 番目の頂点は $ (x_{i,\ j},\ y_{i,\ j}) $ です。 多角形の辺は $ j $ 番目の頂点と $ j+1 $ 番目の頂点を結んでできる線分です(ただし $ M_i+1 $ 番目の頂点は $ 1 $ 番目の頂点とします)。 多角形が単純とは 連続しないどの $ 2 $ 辺も共通部分を持たない(すなわち交差も接触もしない)とき、その多角形を単純といいます。 $ Q $ 個のクエリが与えられます。 $ i\ =\ 1,\ 2,\ \dots,\ Q $ について、$ i $ 個目のクエリは以下の通りです。 - $ N $ 個の多角形のうち、点 $ (X_i\ +\ 0.5,\ Y_i\ +\ 0.5) $ を内部に含むものはいくつありますか？

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M_1 $ $ x_{1,\ 1} $ $ y_{1,\ 1} $ $ x_{1,\ 2} $ $ y_{1,\ 2} $ $ \dots $ $ x_{1,\ M_1} $ $ y_{1,\ M_1} $ $ M_2 $ $ x_{2,\ 1} $ $ y_{2,\ 1} $ $ x_{2,\ 2} $ $ y_{2,\ 2} $ $ \dots $ $ x_{2,\ M_2} $ $ y_{2,\ M_2} $ $ \vdots $ $ M_N $ $ x_{N,\ 1} $ $ y_{N,\ 1} $ $ x_{N,\ 2} $ $ y_{N,\ 2} $ $ \dots $ $ x_{N,\ M_N} $ $ y_{N,\ M_N} $ $ Q $ $ X_1 $ $ Y_1 $ $ X_2 $ $ Y_2 $ $ \vdots $ $ X_Q $ $ Y_Q $

$ Q $ 行出力せよ。 $ i $ 行目には、$ i $ 個目のクエリに対する答えを出力せよ。

### 制約 - $ 1\ \leq\ N\ \leq\ 10^5 $ - $ 4\ \leq\ M_i\ \leq\ 10^5 $ - $ M_i $ は偶数 - $ \sum_i\ M_i\ \leq\ 4\ \times\ 10^5 $ - $ 0\ \leq\ x_{i,\ j},\ y_{i,\ j}\ \leq\ 10^5 $ - $ j\ \neq\ k $ ならば $ (x_{i,\ j},\ y_{i,\ j})\ \neq\ (x_{i,\ k},\ y_{i,\ k}) $ - $ j\ =\ 1,\ 3,\ \dots\ M_i-1 $ について、$ x_{i,\ j}\ =\ x_{i,\ j+1} $ - $ j\ =\ 2,\ 4,\ \dots\ M_i $ について、$ y_{i,\ j}\ =\ y_{i,\ j+1} $ (ただし、$ y_{i,\ M_i\ +1}\ =\ y_{i,\ 1} $ とする) - 与えられる多角形は単純 - $ 1\ \leq\ Q\ \leq\ 10^5 $ - $ 0\ \leq\ X_i,\ Y_i\ \lt\ 10^5 $ - 入力は全て整数 ### Sample Explanation 1 !\[\](https://img.atcoder.jp/ghi/5fccf008dddd93f10ebfc7f13d04a0e0.png) 異なる多角形同士は、交差したり接触したりする可能性があることに注意してください。 ### Sample Explanation 2 !\[\](https://img.atcoder.jp/ghi/1c97f791a2aadcf5637b1f10736fb820.png) 多角形は単純ですが、凸多角形とは限りません。