닮은 삼각형

면접 대비

시간 제한1초메모리 제한1024 MB

요약
정수 좌표로 주어진 두 삼각형이 닮음인지 판정하고, 닮음이면 닮음비의 제곱을 기약분수 p/q로 출력하며 아니면 -1을 출력한다.
난이도

보통10점 중 4점

유형
기하, 수학, 정렬, 정수론
정답자
아직 제출이 없습니다

문제

주쿠는 학교에서 삼각형의 닮음을 배우고 있다. 두 삼각형은 대응하는 각의 크기가 모두 같고 대응하는 변의 길이가 서로 비례할 때 서로 닮음이다. 닮은 두 삼각형은 서로 회전, 대칭(뒤집기), 평행이동되어 있을 수 있다. 닮은 두 삼각형에서 대응하는 변의 길이의 비를 그들의 닮음비라고 한다.

숙제로 주쿠는 여러 쌍의 삼각형을 받았고, 각 쌍의 닮음 관계를 판별해야 한다. 주쿠를 도와, 두 삼각형이 닮았는지 판정하고 닮았다면 그 닮음비를 구하는 프로그램을 작성하라.

입력

첫째 줄에 여섯 개의 정수가 주어진다. 첫 번째 삼각형의 세 꼭짓점의 xx, yy 좌표이며, x1 y1 x2 y2 x3 y3x_1\ y_1\ x_2\ y_2\ x_3\ y_3 순서이다. 각 좌표는 −109-10^9 이상 10910^9 이하이다. 둘째 줄에도 같은 형식으로 여섯 개의 정수가 주어지며, 두 번째 삼각형의 세 꼭짓점 좌표이다. 꼭짓점은 시계 방향 또는 반시계 방향 어느 순서로도 주어질 수 있다. 주어진 세 점은 항상 삼각형을 이룬다(일치하는 점이나 한 직선 위에 놓인 점은 없다).

출력

닮음비를 kk라 하자. 즉 첫 번째 삼각형이 두 번째 삼각형보다 몇 배 큰지를 나타내며, 첫 번째가 더 작으면 k<1k < 1이다. 꼭짓점의 좌표가 모두 정수이므로 각 변의 길이의 제곱은 항상 정수이고, 따라서 k2k^2은 항상 유리수이다(반면 kk 자체는 무리수일 수 있다). 두 삼각형이 닮았다면 k2k^2을 기약분수 p/q 형태로 출력한다. 이때 q≥1q \ge 1이고 gcd⁡(p,q)=1\gcd(p, q) = 1이며, 분모가 11일 때에도 분모를 반드시 함께 출력한다(예: 4/1). 두 삼각형이 닮지 않았다면 -1을 출력한다.

예제4

  1. 예제 1

    입력
    0 0 6 0 0 3
    -1 3 1 -1 -1 -1
    
    예상 출력
    9/4
    
  2. 예제 2

    입력
    0 0 3 0 1 1
    0 0 2 0 1 1
    
    예상 출력
    -1
    
  3. 예제 3

    입력
    0 0 1 0 0 1
    0 0 1 0 0 1
    
    예상 출력
    1/1
    
  4. 예제 4

    입력
    -1 3 1 -1 -1 -1
    0 0 6 0 0 3
    
    예상 출력
    4/9