기하 애호가
시간 제한7초메모리 제한2048 MB
볼록 다각형의 변을 직선으로 연장해 얻은 교점들이 주어질 때, 원래 다각형의 꼭짓점을 정확한 분수 좌표로 복원합니다.
문제
알타이르는 평소처럼 평면 위의 점들을 가지고 놀고 있었다. 어느 날 그는 새로운 게임을 발견했고, 너에게 함께 하자고 했다.
그는 평면 위에 변이 개인 볼록 다각형을 그렸다. 이 다각형의 어떤 두 변도 평행하지 않다. 그다음 그는 각 변을 직선으로 연장하고, 모든 직선 쌍에 대해 교점을 구했다.
이제 그가 얻은 점들을 너에게 준다. 이 점들로부터 처음의 다각형을 구하라.
입력
첫 줄에 점의 개수를 나타내는 정수 ()이 주어진다.
다음 개 줄에는 각각 정수 , , , (, )가 주어진다. 번째 점의 X 좌표는 이고, Y 좌표는 이다. 와 는 서로소이고, 와 도 서로소이다.
주어진 점들로 다각형이 유일하게 정해진다고 보장된다.
출력
첫 줄에 꼭짓점의 개수 를 출력한다.
다음 개 줄에는 각 꼭짓점의 좌표를 , , , 형식으로 출력한다. 꼭짓점은 어떤 순서로 출력해도 된다. 각 와 는 서로소여야 하고, 각 와 도 서로소여야 한다.