별자리 찾기

문제

맑고 달이 없는 밤하늘에는 수백만 개의 별이 반짝인다. 이 압도적인 수의 별 앞에서, 그리스인들은 약 2,000년 전부터 이 혼돈에 질서를 부여하기 시작했다. 그들은 별들을 묶어 별자리를 만들고, 오늘날에도 쓰이는 이름을 붙였다. 예를 들어 "작은곰자리(Ursa Minor)", "물고기자리(Pisces)", "게자리(Cancer)" 등이 있다.

별자리의 그림만 보고 실제 밤하늘에서 그 별자리를 찾는 일은 초보자에게 쉽지 않다. 게다가 별 세 개로만 이루어진 "삼각형자리(Triangulum)"처럼 단순한 별자리의 모양은 하늘에 여러 번 나타날 수 있어, 어느 것이 진짜인지 골라내기 어렵다.

이 문제에서는 컴퓨터로 하늘에서 별자리를 찾는다.

성도(star map)가 주어진다. 성도는 평면 위 점들의 집합이며, 각 점(별)에는 밝기가 하나씩 붙어 있다. 그리고 별자리 역시 평면 위 점들의 집합으로 주어진다. 각 별자리에 대해 다음을 구하라.

그 별자리가 성도에 몇 번 나타나는지, 그리고
나타나는 경우가 하나라도 있다면, 그중 가장 밝은 것의 위치. (이유: 어떤 별자리가 여러 번 나타난 것처럼 보인다면, 가장 밝은 것이 가장 눈에 잘 띄므로 진짜일 가능성이 높다.)

출현(occurrence)이란, 성도의 별들 중 일부를 골라 만든 부분집합으로서, 별자리의 별들을 임의로 회전하거나 크기를 바꾼(rotated and/or scaled) 복사본을 이루는 것을 말한다(평행이동도 허용되지만, 뒤집기(반사)는 허용되지 않는다). 같은 부분집합이 여러 방향으로 별자리에 들어맞을 수도 있다 — 정사각형은 $90^\circ$ 회전에 따라 4가지 방향으로 들어맞는다 — 하지만 같은 부분집합을 회전시킨 이런 경우들은 서로 다른 출현으로 세지 않는다.

출현의 밝기는 그 출현을 이루는 별들의 평균 밝기, 즉 각 별의 밝기의 합을 별자리의 별 개수로 나눈 값이다.

입력

입력은 여러 개의 성도를 담고 있다.

각 성도는 별의 개수 $N$ 이 적힌 한 줄로 시작한다( $1 \le N < 1000$ ). 이어지는 $N$ 개의 줄에는 각각 세 정수, 즉 한 별의 $X$ 좌표, $Y$ 좌표, 밝기가 적혀 있다. 값이 클수록 밝은 별이다.

그다음 줄에는 처리할 별자리의 개수 $M$ 이 적혀 있다( $1 \le M < 50$ ). 각 별자리의 설명은 별자리의 별 개수 $S$ 와 별자리의 이름 $C$ (공백이 없는 40자 이하의 문자열)가 적힌 한 줄로 시작한다. 이어지는 $S$ 개의 줄에는 각각 별자리를 이루는 한 별의 $X$ / $Y$ 좌표가 적혀 있다.

모든 좌표는 $-1000$ 부터 $1000$ 사이이고, 밝기는 $0$ 부터 $100$ 사이이다.

성도와 성도 사이는 빈 줄로 구분된다. 입력은 별이 없는 성도( $N = 0$ )로 끝나며, 이 성도는 처리하지 않는다.

참고: 모든 별의 좌표가 정수이므로, 회전·확대·축소한 별자리의 점이 정수 좌표에 놓이지 않는 경우는 곧바로 제외할 수 있다.

출력

각 성도에 대해, 먼저 성도의 번호를 한 줄에 출력한다. 첫 번째 성도는 Map #1, 두 번째 성도는 Map #2와 같은 식으로 출력한다.

그다음 각 별자리에 대해 — 입력에 주어진 순서대로 — <name> occurs <k> time(s) in the map. 형식의 한 줄을 출력한다. 여기서 <name>은 별자리의 이름이고, <k>는 그 별자리가 나타나는 횟수이다.

<k>가 1 이상이면, 다음 줄에 Brightest occurrence:를 출력하고 이어서 가장 밝은 출현을 이루는 별들의 위치를 출력한다. 각 위치는 (x,y) 형태로 쓰고 하나의 공백으로 구분한다. 위치는 $X$ 좌표의 오름차순으로 출력하며, $X$ 좌표가 같은 별들은 $Y$ 좌표의 오름차순으로 정렬한다. 각 성도에서 모든 별자리는 가장 밝은 출현이 유일하다고 가정해도 된다.

각 별자리를 출력하기 전에 빈 줄을 하나 출력하고, 각 성도를 출력한 뒤에는 다섯 개의 붙임표(-----)로 이루어진 줄을 출력한다.