어파인 변환 복원

시간 제한2초메모리 제한128 MB

요약
정수 좌표 세 개의 시작점과 세 개의 끝점이 주어질 때, 회전 후 격자로 반올림하고 정수 배율과 정수 이동을 적용해 시작 집합을 끝 집합으로 보내는 변환이 존재하는지, 존재한다면 그러한 변환이 평면 전체에서 모두 같은지 판정한다.
난이도

어려움10점 중 9점

유형
기하, 수학, 완전 탐색, 구현
정답자
아직 제출이 없습니다

문제

어떤 그리기 프로그램에는 모든 제어점을 가장 가까운 격자점(정수 좌표를 가진 점)으로 이동시키는 "격자에 맞추기" 기능이 있다. 세 개의 똑같은 표시 점이 그림 위에 찍혔고, 각 점은 격자점에 놓였으므로 그 좌표는 모두 정수이다.

그 뒤 그림은 세 개의 도구로 변형되었고, 변형 후에도 세 점은 새로운 정수 격자 위치로 옮겨진 채 그대로 남아 있었다. 세 도구는 원점을 중심으로 한 회전, 원점을 중심으로 한 크기 조정, 그리고 평행 이동이다. 회전이 가장 먼저 적용되었고, 크기 조정과 평행 이동은 그 뒤에 알 수 없는 순서로 적용되었다(즉 순서는 회전·평행 이동·크기 조정 또는 회전·크기 조정·평행 이동 중 하나였다). 기억하고 있는 제약은 다음과 같다.

  • 크기 조정: x축과 y축 배율은 (음수일 수도 있는) 00이 아닌 정수였고, 크기 조정의 중심은 원점 (0,0)(0,0)이었다.
  • 평행 이동: x축과 y축 이동량은 정수였다.
  • 회전: 원점을 중심으로 한 너비 2020인 정사각형의 둘레 위에 있는 정수 좌표의 점 (x,y)(x, y)로 지정되었다(따라서 −10≤x,y≤10-10 \le x, y \le 10이고, ∣x∣|x| 또는 ∣y∣|y| 중 적어도 하나는 1010이다). 그림은 회전 후 양의 x축이 (x,y)(x, y)를 지나도록 원점을 중심으로 회전되었다.

회전 직후 가장 가까운 격자점으로 맞추기가 일어났다. 소수 부분이 정확히 0.50.5인 좌표는 00에서 멀어지는 방향으로 반올림되었다. 정수 배율의 크기 조정과 정수량의 평행 이동은 정수 좌표를 정수로 유지하므로 추가적인 맞추기는 필요하지 않다.

세 점의 원래 정수 위치와 최종 정수 위치가 주어질 때, 이 변형의 순서를 복원할 수 있는지 판정하여라.

입력

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 −500≤xi,yi≤500-500 \le x_i, y_i \le 500 (1≤i≤61 \le i \le 6)인 여섯 개의 정수 쌍 (xi,yi)(x_i, y_i)로 구성되며, 두 줄에 걸쳐 한 줄에 세 쌍씩 주어진다. 앞의 세 쌍은 세 점의 서로 다른 초기 위치이고, 뒤의 세 쌍은 서로 다른 최종 위치이다. 각 묶음 안에서 세 쌍의 순서는 의미가 없다. 즉, 어떤 초기 점이든 세 최종 위치 중 어느 것에도 대응할 수 있다.

입력은 여섯 개의 00으로 이루어진 줄로 끝나며, 이 줄은 테스트 케이스가 아니다.

출력

각 테스트 케이스마다 케이스 번호 다음에 아래 세 메시지 중 정확히 하나를 출력한다.

  • 유효한 변형이 하나 이상 존재하고 그 모두가 그림 전체에 (그림이 어떻게 생겼든) 같은 효과를 주면 equivalent solutions.
  • 유효한 변형이 여러 개 존재하지만 일반적으로 그 모두가 그림 전체를 같은 방식으로 옮기지는 않으면(두 유효한 변형이 어떤 그림을 서로 다르게 옮기면) inconsistent solutions.
  • 위 두 경우 중 어느 것도 아니면 no solution.

유효한 변형이란, 위의 제약을 지키면서 세 점의 초기 집합을 최종 집합(세 최종 위치를 모두 차지)으로 옮기는 회전·평행 이동·크기 조정의 조합이다(순서는 회전·평행 이동·크기 조정 또는 회전·크기 조정·평행 이동). 출력 형식은 Case X: <message>이다.

예제3

  1. 예제 1

    입력
    3 0 4 0 1 4
    -2 -4 -1 3 3 -4
    0 1 1 1 2 1
    1 2 2 2 3 2
    1 0 2 0 3 0
    3 3 1 1 2 2
    1 0 2 0 3 0
    3 2 1 1 2 2
    2 3 0 6 1 2
    2 3 0 6 1 2
    0 0 0 0 0 0
    
    예상 출력
    Case 1: equivalent solutions
    Case 2: inconsistent solutions
    Case 3: no solution
    Case 4: inconsistent solutions
    Case 5: equivalent solutions
    
  2. 예제 2

    입력
    3 0 4 0 1 4
    -2 -4 -1 3 3 -4
    0 0 0 0 0 0
    
    예상 출력
    Case 1: equivalent solutions
    
  3. 예제 3

    입력
    1 0 2 0 3 0
    3 3 1 1 2 2
    0 0 0 0 0 0
    
    예상 출력
    Case 1: no solution