Final Defense Line

Time Limit : 3 sec, Memory Limit : 65536 KB

最終防衛線

たびたび未確認生物に侵略されるようになった某国では重要施設を新型防衛兵器で保護することにした。
この兵器は多角形の領域に特殊なガスを充満させることで未確認生物にダメージを与えることができる。未確認生物が侵攻する途中でガスの濃度が変わると、濃度の差の絶対値のダメージを与える。ガスの濃度が同じ領域を動いているときはダメージは一切発生しない。
現在の技術ではガスの濃度は一定にしかできないので、某国は新型防衛兵器を複数投入することにした。全ての兵器でガスの濃度は同じであり、複数の兵器の領域に含まれる部分は濃度が足し合わされる。 未確認生物の出現地点と重要施設の位置を元に、未確認生物が重要施設まで侵攻する時に受けるダメージの最小値を求めて欲しい。
ただし、未確認生物の侵攻ルートに多角形の頂点や他の多角形との交点は含まれないものとする。また、多角形の辺上を辺にそって侵攻することはない。

Input

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

多角形の数
多角形の頂点数
x座標 y座標
x座標 y座標
...
多角形の頂点数
x座標 y座標
x座標 y座標
...
出現地点と重要施設のデータの数
出現位置のx座標 出現位置のy座標 重要施設のx座標 重要施設のy座標
出現位置のx座標 出現位置のy座標 重要施設のx座標 重要施設のy座標
...

Constraints

  • 入力に含まれる座標は絶対値が1,000以下の整数
  • 多角形の数は1以上5以下
  • 多角形の頂点数は3以上5以下
  • 出現地点と重要施設のデータの数は1以上100以下
  • 多角形は与えられた頂点を順につないでできる多角形を指し、自己交差はない
  • 出現地点と重要施設は多角形の頂点及び辺上にあることはない

Output

出現地点と重要施設の組ごとに未確認生物が重要施設まで侵攻する際に受けるダメージの最小値を1行ずつ出力せよ。

Sample Input 1

2
4
0 4
1 1
3 1
4 4
3
6 0
10 0
8 7
1
2 3 9 1

Output for the Sample Input 1

2

1つ目の多角形を出る時に1ダメージを与え、2つ目の多角形に入る時に1ダメージを与える。

Sample Input 2

1
4
0 0
10 0
10 10
0 10
2
15 5 5 5
5 5 15 5

Output for the Sample Input 2

1
1

1つ目のデータでは未確認生物が多角形に入る時にダメージが発生する。 2つ目のデータでは未確認生物が多角形から出る時にダメージが発生する。

Sample Input 3

2
4
0 0
10 0
10 10
0 10
4
10 0
20 0
20 10
10 10
1
5 5 15 5

Output for the Sample Input 3

0

未確認生物が1つ目の多角形から2つ目の多角形に動くルートを取ると濃度が変わることがないのでダメージを与えることができない。

Sample Input 4

2
3
0 0
10 0
5 10
3
5 0
15 0
10 10
1
5 5 10 5

Output for the Sample Input 4

2

出現地点の領域と重要施設の領域は点で接しているがこの点を通って侵攻することはない。

Sample Input 5

2
4
0 0
10 0
10 10
0 10
4
0 0
10 0
10 10
0 10
2
15 5 5 5
5 5 15 5

Output for the Sample Input 5

2
2

Source: ACM-ICPC Japan Alumni Group Summer Camp , Day 2, Tokyo, Japan, 2012-09-15
http://acm-icpc.aitea.net/