넓이를 같게

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

요약

N개의 선분이 주어질 때, 각 선분과 만드는 삼각형의 넓이가 모두 같은 점 P가 있는지 판별하고, 있으면 그 유리수 좌표 하나를 구합니다.

난이도: 보통10점 중 7점
유형: 기하, 수학
정답자: 아직 제출이 없습니다

문제

2차원 평면 위에 선분 $N$ 개가 주어진다. 점 $P$ 를 적당히 잡아, 각 선분과 $P$ 가 이루는 삼각형의 넓이가 모두 같게 만들 수 있는지 판별하라. 가능하다면 그러한 점 $P$ 를 하나 구해 보자. 세 점이 한 직선 위에 있으면 그 삼각형의 넓이는 0으로 계산한다.

입력

첫째 줄에 선분의 개수 $N$ 이 주어진다. ( $1 \le N \le 100000$ )

둘째 줄부터 $N$ 개의 줄에 걸쳐 각 선분의 양 끝점 좌표 $x_1$ , $y_1$ , $x_2$ , $y_2$ 가 공백으로 구분되어 주어진다. ( $-10^6 \le x_1, y_1, x_2, y_2 \le 10^6$ )

출력

조건을 만족하는 점 $P$ 가 없으면 첫째 줄에 NO를 출력한다.

조건을 만족하는 점 $P$ 가 있으면 첫째 줄에 YES를 출력한다. 둘째 줄에는 $P$ 의 $x$ 좌표를, 셋째 줄에는 $y$ 좌표를 각각 $a / b$ 형태로 출력한다. 여기서 $a$ 와 $b$ 는 절댓값이 $10^{40}$ 보다 작은 정수이고, $\gcd(a, b) = 1$ 이며 $b > 0$ 이어야 한다.

답이 YES이면 출력 조건을 만족하는 유리수 점 $P$ 가 존재함을 증명할 수 있다.

예제1

예제 1
입력
```
3
0 0 1 0
2 0 2 1
2 2 0 1
```
예상 출력
```
YES
4/1
2/1
```