B. 아핀 대소동

Tess L. Ation은 지난주 자신의 새 드로잉 소프트웨어 베타 버전을 시연하다가 작은 문제에 부딪혔다. 화면에는 프로그램의 모든 기능을 보여 주는 우아한 시연용 디자인이 있었는데, 이를 만드는 데 몇 시간이나 걸렸다. 잠재 투자자들이 시연을 보러 방에 들어왔을 때 그녀는 마지막 손질을 하고 있었다. 발표는 순조로웠다. 발표가 끝날 무렵 Tess는 제어판 버튼을 클릭하며 청중에게 말했다. “이것은 ‘격자에 맞추기(snap to grid)’ 기능입니다. 꼭짓점 같은 제어점을 가장 가까운 격자점으로 이동시키죠. 보여 드릴게요.” 그리고 화면에 밝은 빨간 점 세 개를 찍었다. 각 점은 클릭한 위치에서 가장 가까운 격자점에 나타났다. (“다행히 내 시연 디자인의 제어점은 모두 이미 정수 좌표에 있었어. 하지만 다이어그램을 저장하기 전에 이 빨간 점 세 개를 지워야 한다는 걸 잊지 말아야지.” 하고 그녀는 생각했다.) “이제 옆방으로 가서 여러분끼리 시스템에 대해 의논하고 화면을 자세히 보실 수 있게 자리를 비켜 드리겠습니다. 다만 아직 파일을 저장하지 않았으니 아무것도 건드리지 말아 주세요.” 몇 분 뒤 일행이 Tess에게 왔다. 방문객 한 명이 Tess에게 다가와 말했다. “괜찮으시다면, 제가 직접 써 보고 싶었어요. 걱정 마세요, \(x-sc\)ale과 \(y-sc\)ale 컨트롤만 조금 만졌어요.” 다음 사람이 말했다. “문제가 되면 죄송한데, 화면 표시 속도를 꼭 느껴 보고 싶어서 평행 이동 도구를 좀 만져 봤어요.” 세 번째 사람이 말했다. “아주 작은 테스트 하나를 참을 수 없었어요. 회전 후에 모든 꼭짓점이 가장 가까운 격자점에 맞춰지는 걸 보려고 이미지를 회전시켜 봤어요.” 회전 도구를 만진 사람은 자신이 첫 번째였다고 기억했지만, 나머지 두 사람은 순서를 기억하지 못했다. 세 사람은 변경 내용의 몇 가지 세부 사항만 기억했다. x축·y축 확대 배율(\(x- an\)d \(y-sc\)aling factors)은 0이 아닌(n\(on- ze\)ro), 음수일 수도 있는 정수였고, 확대의 중심은 원점 (0, 0)이었다. x축·y축 평행 이동량(\(x- an\)d \(y-tr\)anslation amounts)은 정수였다. 회전은 원점을 중심으로 하는 너비 20인 정사각형 둘레 위의 정수 좌표 점 (x, y)로 지정되었다(따라서 −\(10 \le x\), \(y \le 10\)이고 \(x\) 또는 \(y\) 또는 둘 다의 절댓값이 10이었다). 이 도구는 회전 후 양의 \(x-ax\)is가 (x, y)를 지나도록 그림을 원점 중심으로 회전시켰다. 격자에 맞추기는 이 회전 뒤에 수행되었다(소수 부분이 0.5인 좌표는 0에서 멀어지는 방향으로 반올림되었다). 그들이 떠난 뒤 Tess가 자신의 디자인을 보니 완전히 바뀌어 있었다! 아직 “실행 취소” 기능을 구현하지 않았고, 시연 전에 다이어그램을 저장하지도 않았다. 하지만 세 개의 동일한 빨간 점은 (물론 다른 정수 격자 위치로 변환된 채) 여전히 남아 있었고, Tess는 처음에 점을 찍었던 정수 좌표를 기억할 수 있었다. 물론 다른 누군가가 말없이 그림을 더 바꿨을 수도 있지만, 변경 순서를 재구성하는 것이 가능한지 확인하는 프로그램을 짤 수는 있었다. 당신도 할 수 있는가?

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 여섯 쌍의 정수 \(xi\)와 \(yi\) (−\(500 \le xi\), y\(i \le 500\), \(1 \le i \le 6\))로 이루어지며, 한 줄에 세 쌍씩 주어진다. 앞의 세 쌍은 세 빨간 점의 서로 다른 초기 위치를 나타낸다. 뒤의 세 쌍은 세 점의 서로 다른 최종 위치를 나타낸다. 각 세 쌍 묶음 안에서 쌍의 순서는 의미가 없다. 예를 들어 (\(x\)1, y1)은 (\(x\)4, y4), (\(x\)5, y5), (\(x\)6, y6) 중 어느 것으로든 이동했을 수 있다. 마지막 테스트 케이스 다음에는 0 여섯 개가 있는 한 줄이 주어진다.

각 테스트 케이스마다 케이스 번호와 함께 다음 세 메시지 중 하나를 출력한다.

• “equivalent solutions”: 유효한 변환이 하나 이상 존재하고, (전체 그림이 어떤 모양이든) 그 변환들이 모두 전체 그림에 같은 효과를 낸다는 뜻이다.

• “inconsistent solutions”: 유효한 변환이 여러 개 있지만, 일반적으로 모든 변환이 전체 그림을 같은 방식으로 옮기지는 않는다는 뜻이다(어떤 그림은 두 유효한 변환(transfor\(ma- ti\)ons)에 의해 서로 다르게 옮겨진다).

• “no solution”: 위의 두 경우 모두 해당하지 않는다는 뜻이다. 유효한 변환이란 위에서 설명한 제한을 만족하며 빨간 점들의 초기 집합을 (세 최종 위치를 모두 차지하도록) 최종 집합으로 옮기는 회전, 평행 이동, 확대의 조합(회전, 확대, 평행 이동 순서일 수도 있음)이다. 샘플 출력의 형식을 따른다.

생성자가 기록되지 않았습니다.

출처 ICPC World Finals 2011