생체 인식

최근 생체 인식(biometrics)이라는 용어는 망막이나 홍채 스캔, 지문, 얼굴 인식처럼 생물학적 특징을 이용해 개인을 식별하는 신기술 분야를 가리키는 말로 쓰인다.

간단한 생체 인식 시스템은 사람의 이미지에서 눈, 코, 귀 등 특정 특징들을 꼭짓점으로 보고 이 꼭짓점들을 선분으로 이어 하나의 다각형으로 변환한다. 이 다각형의 꼭짓점은 모두 서로 다르지만, 선분끼리 서로 교차할 수 있어 다각형이 자기 교차(degenerate)하는 형태일 수도 있다. 이러한 다각형은 보통 멀리서 찍은 이미지로부터 만들어지므로 크기와 회전 방향이 불확실하다.

두 다각형이 서로 닮았는지, 즉 평행이동, 회전, 확대/축소만으로 한 다각형을 다른 다각형에 완전히 겹치게 만들 수 있는지 판정하여라. 단, 뒤집기(반사)는 허용되지 않는다.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 다음과 같이 구성된다.

• 특징의 개수 $f$
• 첫 번째 다각형의 꼭짓점 $f$개의 좌표쌍
• 두 번째 다각형의 꼭짓점 $f$개의 좌표쌍

두 다각형의 꼭짓점은 같은 특징들의 집합을 같은 순서로 나타낸다. 예를 들어 오른쪽 귀끝, 턱, 오른쪽 눈, 코, 왼쪽 눈, 왼쪽 귀끝, 앞니 사이 등이다. 각 다각형은 서로 다른 $f$개의 꼭짓점을 가지며, 각 꼭짓점은 정수 $x$, $y$ 좌표쌍으로 주어진다. 특징의 개수는 $3$개 이상 $10$개 이하이고, 좌표는 모두 $-1000$ 이상 $1000$ 이하의 정수이다. 마지막 테스트 케이스 다음에는 $0$ 하나만 있는 줄이 온다.

각 테스트 케이스마다 두 다각형이 닮았으면 similar, 닮지 않았으면 dissimilar를 한 줄에 출력한다. 두 다각형은 평행이동, 회전, 확대/축소(반사 제외)를 적절히 조합하여 각 특징에 대응하는 두 꼭짓점이 모두 같은 위치에 오도록 만들 수 있을 때 서로 닮았다고 한다.