만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

기하 애호가

시간 제한7초메모리 제한2048 MB

요약
볼록 다각형의 변을 직선으로 연장해 얻은 교점들이 주어질 때, 원래 다각형의 꼭짓점을 정확한 분수 좌표로 복원합니다.
난이도

어려움10점 중 9점

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

문제

알타이르는 평소처럼 평면 위의 점들을 가지고 놀고 있었다. 어느 날 그는 새로운 게임을 발견했고, 너에게 함께 하자고 했다.

그는 평면 위에 변이 kk개인 볼록 다각형을 그렸다. 이 다각형의 어떤 두 변도 평행하지 않다. 그다음 그는 각 변을 직선으로 연장하고, 모든 직선 쌍에 대해 교점을 구했다.

이제 그가 얻은 점들을 너에게 준다. 이 점들로부터 처음의 다각형을 구하라.

입력

첫 줄에 점의 개수를 나타내는 정수 nn (1≤n≤2001 \le n \le 200)이 주어진다.

다음 nn개 줄에는 각각 정수 pxp_x, qxq_x, pyp_y, qyq_y (−106≤px,py≤106-10^6 \le p_x, p_y \le 10^6, 1≤qx,qy≤1061 \le q_x, q_y \le 10^6)가 주어진다. ii번째 점의 X 좌표는 px/qxp_x / q_x이고, Y 좌표는 py/qyp_y / q_y이다. pxp_x와 qxq_x는 서로소이고, pyp_y와 qyq_y도 서로소이다.

주어진 점들로 다각형이 유일하게 정해진다고 보장된다.

출력

첫 줄에 꼭짓점의 개수 kk를 출력한다.

다음 kk개 줄에는 각 꼭짓점의 좌표를 pxp_x, qxq_x, pyp_y, qyq_y 형식으로 출력한다. 꼭짓점은 어떤 순서로 출력해도 된다. 각 pxp_x와 qxq_x는 서로소여야 하고, 각 pyp_y와 qyq_y도 서로소여야 한다.

예제1

  1. 예제 1

    입력
    6
    1 1 2 1
    12 5 24 5
    0 1 0 1
    3 1 3 1
    -3 1 0 1
    4 1 0 1
    
    예상 출력
    4
    0 1 0 1
    1 1 2 1
    3 1 3 1
    4 1 0 1