어파인 변환 복원
시간 제한2초메모리 제한128 MB
정수 좌표 세 개의 시작점과 세 개의 끝점이 주어질 때, 회전 후 격자로 반올림하고 정수 배율과 정수 이동을 적용해 시작 집합을 끝 집합으로 보내는 변환이 존재하는지, 존재한다면 그러한 변환이 평면 전체에서 모두 같은지 판정한다.
문제
어떤 그리기 프로그램에는 모든 제어점을 가장 가까운 격자점(정수 좌표를 가진 점)으로 이동시키는 "격자에 맞추기" 기능이 있다. 세 개의 똑같은 표시 점이 그림 위에 찍혔고, 각 점은 격자점에 놓였으므로 그 좌표는 모두 정수이다.
그 뒤 그림은 세 개의 도구로 변형되었고, 변형 후에도 세 점은 새로운 정수 격자 위치로 옮겨진 채 그대로 남아 있었다. 세 도구는 원점을 중심으로 한 회전, 원점을 중심으로 한 크기 조정, 그리고 평행 이동이다. 회전이 가장 먼저 적용되었고, 크기 조정과 평행 이동은 그 뒤에 알 수 없는 순서로 적용되었다(즉 순서는 회전·평행 이동·크기 조정 또는 회전·크기 조정·평행 이동 중 하나였다). 기억하고 있는 제약은 다음과 같다.
- 크기 조정: x축과 y축 배율은 (음수일 수도 있는) 이 아닌 정수였고, 크기 조정의 중심은 원점 이었다.
- 평행 이동: x축과 y축 이동량은 정수였다.
- 회전: 원점을 중심으로 한 너비 인 정사각형의 둘레 위에 있는 정수 좌표의 점 로 지정되었다(따라서 이고, 또는 중 적어도 하나는 이다). 그림은 회전 후 양의 x축이 를 지나도록 원점을 중심으로 회전되었다.
회전 직후 가장 가까운 격자점으로 맞추기가 일어났다. 소수 부분이 정확히 인 좌표는 에서 멀어지는 방향으로 반올림되었다. 정수 배율의 크기 조정과 정수량의 평행 이동은 정수 좌표를 정수로 유지하므로 추가적인 맞추기는 필요하지 않다.
세 점의 원래 정수 위치와 최종 정수 위치가 주어질 때, 이 변형의 순서를 복원할 수 있는지 판정하여라.
입력
입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 ()인 여섯 개의 정수 쌍 로 구성되며, 두 줄에 걸쳐 한 줄에 세 쌍씩 주어진다. 앞의 세 쌍은 세 점의 서로 다른 초기 위치이고, 뒤의 세 쌍은 서로 다른 최종 위치이다. 각 묶음 안에서 세 쌍의 순서는 의미가 없다. 즉, 어떤 초기 점이든 세 최종 위치 중 어느 것에도 대응할 수 있다.
입력은 여섯 개의 으로 이루어진 줄로 끝나며, 이 줄은 테스트 케이스가 아니다.
출력
각 테스트 케이스마다 케이스 번호 다음에 아래 세 메시지 중 정확히 하나를 출력한다.
- 유효한 변형이 하나 이상 존재하고 그 모두가 그림 전체에 (그림이 어떻게 생겼든) 같은 효과를 주면
equivalent solutions. - 유효한 변형이 여러 개 존재하지만 일반적으로 그 모두가 그림 전체를 같은 방식으로 옮기지는 않으면(두 유효한 변형이 어떤 그림을 서로 다르게 옮기면)
inconsistent solutions. - 위 두 경우 중 어느 것도 아니면
no solution.
유효한 변형이란, 위의 제약을 지키면서 세 점의 초기 집합을 최종 집합(세 최종 위치를 모두 차지)으로 옮기는 회전·평행 이동·크기 조정의 조합이다(순서는 회전·평행 이동·크기 조정 또는 회전·크기 조정·평행 이동). 출력 형식은 Case X: <message>이다.