B - 天体位置観測
Editorial
/ 
/ 
Time Limit: 5 sec / Memory Limit: 256 MB
問題文
ヨシオくんは天体観測が趣味のナイスガイです。
今夜もいつものように、窓から見える夜空に、自分が考えた星座を見つけて数える遊びを始めました。
ヨシオくんは夜空の星からいくつかの星を選び、それらの星の位置関係が特定の星座と完全に一致した場合に、その星座が1回出現したと数えます。
同じ星座になる星の組み合わせが複数組ある場合、その全てを1つの星座の出現回数として数えます。
また、星座の反転・回転・拡大縮小はしません。
例えば、夜空の星が以下の位置関係である場合を考えます。(oが星のある位置で、.が空白)
o.. .o. ..o
この夜空の中には、
o
という星座は3回出現します。
o. .o
という星座は2回出現します。このとき、夜空の中央の星は2回使用されます。
o.. ... ..o
という星座は1回出現します。星座に存在しない夜空の中央の星は無視します。
o... .... .... ...o
という星座は出現しません。
夜空の星の並びと星座が与えられるので、星座が夜空に何回出現しているか数えるプログラムを作成してください。
入力
入力は以下の形式で標準入力から与えられる。
N M X1 Y1 : XN YN L1 SX1,1 SY1,1 : SX1,L1 SY1,L1 : LM SXM,1 SYM,1 : SXM,LM SYM,LM
- 1 行目には、夜空の星の個数 N (1 \leq N \leq 105) と探したい星座の個数 M (1 \leq M \leq 100) が与えられる。
- 2 行目から N 行は、i 番目の夜空の星の位置の座標 Xi(0 \leq Xi \leq 106) と Yi(0 \leq Yi \leq 106) が与えられる。
- p \neq q ならば、Xp \neq Xq または Yp \neq Yq を満たす。
- N+2 行目以降は、下記が M 回繰り返される。
- j 番目の星座に含まれる星の個数 Lj (1 \leq Lj \leq 100) が与えられる。
- 続く Lj 行は、j 番目の星座の k 番目の星の位置の座標 SXj,k(0 \leq SXj,k \leq 9) と SYj,k(0 \leq SYj,k \leq 9) が与えられる。
- p \neq q ならば、SXj,p \neq SXj,q または SYj,p \neq SYj,q を満たす。
部分点
- N \leq 100のケースすべてに正解した場合、部分点として 40 点を与える。
出力
夜空に表われるそれぞれの星座の出現回数を 1 行づつ合計 M 行で出力せよ。出力の末尾には改行をいれること。
入力例1
3 4 1 1 2 2 3 3 1 0 0 2 0 0 1 1 2 0 0 2 2 2 0 0 3 3
出力例1
3 2 1 0
これは問題文で与えられた例と同じであり、上から順に3, 2, 1, 0となる。
入力例2
11 4 21 11 21 12 21 13 21 14 22 11 23 11 24 11 22 13 23 12 23 13 24 13 3 1 1 2 1 1 2 3 1 1 1 2 2 2 3 3 2 2 3 3 3 3 3 3 4 3 4 4
出力例2
3 2 1 1
与えられた夜空の星は、以下の位置関係である。
oooo o.o. oooo o...
これに対して与えられた星座は、
oo o.
o. oo
.o oo
oo .o
という配置なので上から順に3, 2, 1, 1となる。