题目描述

在一个晴朗无月的夜晚，你可以看到天空中闪烁着数百万颗星星。面对如此众多的星星，大约 2000 年前希腊人开始尝试为这一片混乱赋予一些秩序。他们识别出了一些星星群组，称之为星座，并给它们命名，这些名字大多源自希腊神话，且至今仍在使用。例如 “小熊座（Ursa Minor）”、“双鱼座（Pisces）”、“巨蟹座（Cancer）” 以及其他许多星座。

对于业余爱好者来说，仅依据星座的草图，要在天空中实际找到该星座并非易事。此外，像 “三角座（Triangulum）” 这样简单的星座（仅由三颗星星组成），可能会在天空中出现多次。同样，挑出 “正确” 的那一组也并非易事。

传统上，人们会印制星图来解决这个问题。但在本题中，我们将了解计算机如何帮助我们在天空中找到星座。

你会得到一张星图，为简单起见，它是平面上的一组点，每个点都关联着一定的亮度。然后，给定一个星座，同样表示为平面上的一组点，你需要确定：

1. 该星座在星图中出现的次数；
2. 如果存在，找出最亮的那一次出现的位置。（这样做的依据是：如果一个星座似乎在天空中出现了多次，那么最亮的那一组最有可能是真正的星座，因为它是最引人注目的。）

一次出现是指星图中的一组星星，它们构成了与给定星座（可能经过任意旋转和/或缩放）相同的形状。

一次出现的亮度是指它所包含的星星的平均亮度，即各个星星亮度之和除以该星座的星星数量。

输入格式

输入文件包含多个星图的描述。每个星图以一行开头，该行包含一个整数 $n$，表示星图中星星的数量$（1 <= n < 1000）$。接下来的 $n$ 行，每行包含三个整数，分别是每颗星星的 $x$ 坐标、$y$ 坐标和亮度。数值越大，星星越亮。

下一行包含一个整数 $m$，表示接下来要给出的星座数量$（1 <= m < 50）$。每个星座的描述以一行开头，该行包含一个整数 $si$，表示星座 $i$ 中星星的数量，以及一个字符串 $Ni$，即该星座的名称（$Ni$ 由不超过 40 个字符组成，且不包含空格）。接下来的 $si$ 行包含该星座星星的坐标，同样以 $x$/$y$ 坐标对的形式给出。

星图之间用一个空行分隔。输入文件以一个空的星图$（n = 0）$结束，这个空星图不需要处理。

注意：由于所有星星的坐标都是整数，你可以很容易地排除那些点的坐标不是整数的旋转或缩放后的星座。

输出格式

对于每个星图，首先在单独的一行上输出星图的编号（“Map #1”、“Map #2” 等）。

对于每个星座，按照输入中的顺序，首先在一行上输出它的名称以及在星图中出现的次数，格式如输出示例所示。

如果至少有一次出现，输出最亮的那一次出现的位置，方法是列出构成最亮出现的星星的位置。星星的位置必须按照 $x$ 坐标升序打印。如果 $x$ 坐标相同，则按照 $y$ 坐标升序排序。如果有多个同样亮的解，只输出其中一个。请遵循示例输出中的格式。

在每个星座之前输出一个空行，在每个星图之后输出一行由 5 个破折号组成的线（“-----”）。

6
1 2 1
2 1 4
2 4 3
3 2 1
4 1 5
4 3 2
2
3 Triangulum
1 1
3 1
2 4
4 Cancer
1 3
4 3
6 1
7 5

0

Map #1

Triangulum occurs 2 time(s) in the map.
Brightest occurrence: (1,2) (4,1) (4,3)

Cancer occurs 0 time(s) in the map.
-----

来源

1996年西南欧洲区域竞赛