Stained Glass

Time limit2sMemory limit128 MB

Summary

Given N lines with fixed directions that may be shifted freely, arrange them to maximize the number of regions and output that maximum.

Level: Medium6 of 10
Topics: Hash map, Combinatorics, Math, Geometry
Solved: No attempts yet

Problem

Mr. Wincenty is delighted that he finally solved his garden problem. With the free time he suddenly gained, he decided to pursue one of his many interests: designing stained glass.

He sat down at his desk with a pencil and ruler, prepared a sheet of thick paper, and drew $N$ straight lines across it. When he finished, he counted how many pieces the lines had cut the sheet into, and found the number smaller than he had hoped. "Maybe I should slide the lines around in my design," he wondered.

Each line may be translated (shifted) freely in the plane, but its direction (slope) must stay the same. Compute the maximum number of pieces (regions) the sheet can be divided into.

Input

The first line contains one integer $N$ ( $1 \le N \le 200000$ ), the number of lines. Each of the next $N$ lines describes one line.

Each line is given by four space-separated integers $X_1, Y_1, X_2, Y_2$ ( $-10000000 \le X_1, Y_1, X_2, Y_2 \le 10000000$ ), denoting the straight line passing through the two points $(X_1, Y_1)$ and $(X_2, Y_2)$ . The two points describing a line are always distinct.

Output

Output a single line with the maximum number of pieces described above.

Examples1

Example 1
Input
```
3
-1 -1 1 1
0 -1 0 1
-1 0 1 0
```
Expected output
```
7
```