당구

당구(pool)는 북미에서 인기 있는 게임이다. 직사각형 당구대 위에서 진행하며, 당구대에는 여섯 개의 포켓이 있다. 네 모서리에 하나씩, 그리고 긴 두 변의 중앙에 각각 하나씩 있다. 게임의 목표는 큐볼(cue ball)을 쳐서 다른 공과 충돌시켜 포켓에 넣는 것이다.

이 문제의 당구대 표면은 108″ × 54″ 크기이며, 계산을 쉽게 하기 위해 좌표평면 위에 놓는다. 남서쪽 모서리를 (0, 0), 북동쪽 모서리를 (108, 54)에 둔다. 따라서 1번부터 6번까지 번호가 매겨진 여섯 포켓의 중심 좌표는 각각 (0, 0), (54, 0), (108, 0), (0, 54), (54, 54), (108, 54)이다(그림 2 참고). 당구공은 구 형태이며 지름은 2″이다.

그림 2: 당구대 도식.

큐볼, 목적구(target ball), 그리고 당구대 위의 다른 공들의 위치가 주어질 때, 특정 샷을 성공시킬 수 있는지 판정하는 프로그램을 작성하라. 큐볼은 어느 방향으로든 직선으로 칠 수 있다. 공들 사이의 충돌은 완전 탄성 충돌로 가정하므로, 목적구는 항상 큐볼이 접촉한 표면상의 지점에서 멀어지는 방향의 직선으로 움직인다(그림 3 참고).

그림 3: 당구공 충돌 도식.

큐볼을 쳐서 목적구에 직접 충돌시키고, 그 결과 목적구가 곧바로 포켓에 들어가게 만들 수 있으면 그 샷은 가능한 것으로 본다. 두 공 모두 다른 어떤 공과도 충돌해서는 안 되고, 당구대 가장자리(쿠션)에 튕겨서도 안 되며, 공의 중심이 당구대 경계를 벗어나서도 안 된다. 즉, 뱅크 샷, 콤비네이션 샷, 스핀 샷 등 어떤 트릭 샷도 고려하지 않는다. 큐볼의 입사 방향과 목적구의 진행 방향 사이의 각도 차이는 90°보다 커야 함에 유의하라. 목적구의 중심이 포켓의 중심과 정확히 일치하면 그 포켓에 들어간 것으로 본다.

큐볼은 목적구와 접촉하는 즉시 사라진다고 가정해도 된다.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에는 네 개의 실수 xc yc xt yt가 주어지며, (xc, yc)는 큐볼의 위치, (xt, yt)는 목적구의 위치이다. 둘째 줄에는 정수 n(0 ≤ n ≤ 14), 즉 당구대 위에 있는 추가 공의 개수가 주어지고, 이어서 n개의 실수 쌍 x1 y1 … xn yn이 주어진다. 여기서 (xi, yi)는 i번째 추가 공(방해가 될 수 있는 공)의 위치이다. 어떤 두 공도 겹치지 않으며, 모든 공은 당구대 내부에 엄격히 위치한다. 특히 주어지는 모든 좌표는 3 < x < 105, 3 < y < 51을 만족한다.

입력의 끝은 0 하나만 있는 줄로 표시되며, 이 줄은 처리하지 않는다.

각 테스트 케이스마다, 목적구를 넣을 수 있는 포켓의 번호를 오름차순으로 정렬하여 한 줄에 출력한다. 포켓 번호는 공백 하나로 구분한다. 성공 가능한 샷이 하나도 없으면 no shot을 출력한다.