← 返回题目列表

AtCoder · tenka1_2014_final_b

B. 天体位置観测

中文机器翻译题面 查看原题

問題文

吉雄是个以天体观测为爱好的好人。

今晚也像往常一样,他开始在窗外看到的夜空中,寻找自己想象的星座并开始数数的游戏。

吉雄从夜空中的星星中选出一些星,如果这些星的相对位置与特定星座完全一致,就认为那个星座出现了一次。

如果有多个组合的星会形成同一个星座,则全部计为该星座的一次出现。

另外,不会对星座进行翻转、旋转或缩放。

例如,考虑夜空中的星星具有以下位置关系的情况。(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 第n颗夜空中星星的位置坐标 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 第n个星座包含的星星数量 Lj (1 \leq Lj \leq 100) 。 表示
    • 继续 Lj 行是、j 第n个星座的 k 第m颗星的位置坐标 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。