삼각형 동치 변형
시간 제한2초메모리 제한512 MB
넓이가 같은 두 삼각형이 주어질 때, 첫 번째를 두 번째에 정확히 포갤 수 있는 최소 연산 수를 구한다.
문제
평면 위에 넓이가 같은 두 삼각형 과 가 있다. 아래 연산을 에 여러 번 적용해서 을 에 정확히 겹쳐야 한다. 이때 의 꼭짓점은 의 어느 꼭짓점 위에 놓여도 된다. 을 에 겹치는 데 필요한 연산의 최소 횟수를 구하라.
연산: 삼각형의 꼭짓점 하나를 고르고, 그 꼭짓점을 지나면서 마주 보는 변과 평행한 직선 위의 임의의 점으로 옮긴다.
연산 예시
아래 그림은 예제 입력의 첫 번째 데이터셋을 푸는 연산 순서 하나다.
입력
입력은 최대 2000개의 데이터셋으로 이루어지고, 각 데이터셋의 형식은 다음과 같다.
x11 y11
x12 y12
x13 y13
x21 y21
x22 y22
x23 y23
와 는 의 번째 꼭짓점의 좌표와 좌표다.
각 데이터셋은 다음 조건을 만족한다.
- 모든 좌표는 절댓값이 1000 이하인 정수다.
- 과 의 넓이는 서로 같고 0보다 크다.
- 주어지는 여섯 꼭짓점은 모두 서로 다른 점이다.
데이터셋 사이에는 빈 줄이 하나씩 놓인다. 입력은 파일 끝에서 끝난다.
출력
각 데이터셋마다 필요한 연산의 최소 횟수를 한 줄에 출력한다. 연산이 다섯 번 이상 필요하면 횟수 대신 Many를 출력한다.
꼭짓점을 옮긴 뒤의 좌표는 정수가 아니어도 된다.
위 조건을 만족하는 모든 입력에서 필요한 연산 횟수가 어떤 상수 이하임을 증명할 수 있다.