Equal Areas

Time limit1sMemory limit1024 MB

Summary

Given N segments, decide whether a point P exists whose triangle with each segment has the same area, and output one such rational point.

Level: Medium7 of 10
Topics: Geometry, Math
Solved: No attempts yet

Problem

There are $N$ line segments on a two-dimensional plane. Decide whether a point $P$ exists such that the triangle formed by $P$ and each segment has the same area. If such a point exists, find one of them. If three points lie on one line, the area of the triangle formed by them is 0.

Input

The first line contains $N$ , the number of segments. ( $1 \le N \le 100000$ )

Each of the next $N$ lines contains the coordinates of the two endpoints of one segment, $x_1$ , $y_1$ , $x_2$ , $y_2$ , separated by spaces. ( $-10^6 \le x_1, y_1, x_2, y_2 \le 10^6$ )

Output

If no point $P$ satisfies the condition, print NO on the first line.

If a point $P$ satisfies the condition, print YES on the first line. On the second line, print the x-coordinate of $P$ , and on the third line, print the y-coordinate of $P$ , each in the form $a / b$ . Here $a$ and $b$ are integers with absolute value less than $10^{40}$ , $\gcd(a, b) = 1$ , and $b > 0$ .

If the answer is YES, it can be proven that a rational point $P$ satisfying the output conditions exists.

Examples1

Example 1
Input
```
3
0 0 1 0
2 0 2 1
2 2 0 1
```
Expected output
```
YES
4/1
2/1
```