닮은 다각형

아직 제출이 없습니다시간 제한1초메모리 제한1024 MB

문제

두 다각형은 대응하는 각의 크기가 모두 같고 대응하는 변의 길이가 모두 같은 비율을 이룰 때 닮음이라고 한다. 닮은 두 다각형은 서로 회전, 대칭(뒤집기), 평행이동되어 있을 수 있다. 대응하는 변의 길이의 비를 두 다각형의 닮음비라고 한다.

두 다각형이 주어질 때, 두 다각형이 서로 닮았는지 판정하고, 닮았다면 크기 관계와 꼭짓점의 대응 관계를 구하여라.

입력

첫째 줄에 각 다각형의 꼭짓점 개수 $N$이 주어진다 ($3 \le N \le 200,000$).

둘째 줄에는 첫 번째 다각형의 꼭짓점 좌표가 순서대로 $2 \cdot N$개의 정수로 주어진다: $x_1\ y_1\ x_2\ y_2\ \dots\ x_N\ y_N$. 각 좌표는 $-10^9$ 이상 $10^9$ 이하의 정수이다.

셋째 줄에는 같은 형식으로 두 번째 다각형의 꼭짓점 좌표가 주어진다.

각 다각형의 꼭짓점은 시계 방향 또는 반시계 방향 중 어느 순서로도 주어질 수 있다. 주어지는 점들은 항상 겹치는 꼭짓점이 없고, $180^\circ$(평각)인 내각이 없으며, 자기 자신과 교차하지 않는 올바른 단순 다각형을 이룬다.

출력

두 다각형이 닮지 않았다면, 한 줄에 $-1$을 출력한다.

닮았다면 두 줄을 출력한다.

  • 첫째 줄: 닮음비의 제곱 값(첫 번째 다각형이 두 번째 다각형보다 몇 배 큰지를 제곱한 값이며, 두 다각형의 넓이의 비와 같다)을 기약분수 $p/q$ 꼴로 출력한다. 여기서 $p$, $q$는 $\gcd(p, q) = 1$인 양의 정수이다. 이 값은 항상 유리수이므로 정확히 표현할 수 있으며, 두 다각형이 합동이면 $1/1$이다.
  • 둘째 줄: 어떤 닮음 변환(회전, 대칭, 평행이동, 크기 조절)에 의해 첫 번째 다각형의 첫 번째 꼭짓점에 대응될 수 있는 두 번째 다각형의 꼭짓점 번호 중 가장 작은 값을 출력한다. 각 다각형의 꼭짓점은 입력에 주어진 순서대로 $1$번부터 번호를 매긴다.