Number of Polygons

Time limit2sMemory limit128 MB

Summary

Given up to 50 lines defined by point pairs, compute the number of bounded convex polygonal regions formed by their arrangement.

Level: Medium7 of 10
Topics: Geometry, Math, Union-find, Combinatorics
Solved: No attempts yet

Problem

A very large sheet of paper is identified with the XY coordinate plane. Dasom drew N straight lines on it. Each input row gives two distinct points, and the full straight line passing through those points is drawn.

The drawn lines partition the plane into regions. Every bounded region in a line arrangement is a convex polygon whose interior is not crossed by any drawn line. Given the two points that determine each line, compute how many such polygonal regions are formed.

Input

The first line contains the number of lines N. N is a positive integer not greater than 50.

Each of the next N lines contains four integers x1, y1, x2, y2: the coordinates of two distinct points on one line, in order. Every coordinate is between -10,000 and 10,000 inclusive. No input line description is repeated exactly.

Output

Print the number of polygonal regions.

Examples7

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

Example 3

Input

7
-10000 -9999 -10000 9999
-9999 10000 9999 10000
10000 9999 10000 -9999
-9999 -10000 9999 -10000
0 0 0 1
500 0 500 -1
-500 0 -500 -2

Expected output

Example 4

Input

Expected output

Example 5

Input

7
-1 -1 1 1
-1 -2 1 0
-1 0 1 2
-1 0 -1 -10000
1 10000 1 0
3 1 -3 -2
-3 -5 3 4

Expected output

Example 6

Input

5
-100 -100 100 99
-100 -99 100 100
-100 -98 100 101
-100 -97 100 102
-100 -96 100 103

Expected output

Example 7

Input

6
-100 -100 100 99
-100 -99 100 100
-100 -98 100 101
-100 -97 100 102
-100 -96 100 103
1 -1 -2 2

Expected output