Lines

Time limit1sMemory limit1024 MB

Summary

Given N lines in the plane, some possibly coincident, count the regions they divide the plane into. Use Euler's formula with distinct intersection points.

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

Problem

The input gives $N$ lines $\ell_1, \ell_2, \ldots, \ell_N$ in the plane. Write a program that finds the number of regions the plane is divided into by these lines. Some of the lines may coincide.

In the figure below, the plane is divided into 14 regions.

Input

The input consists of $N + 1$ lines. The first line contains $N$ ( $1 \le N \le 1000$ ). The $(i + 1)$ -th line ( $1 \le i \le N$ ) contains four integers $a_i, b_i, c_i, d_i$ ( $0 \le a_i, b_i, c_i, d_i \le 1000$ , $(a_i, b_i) \ne (c_i, d_i)$ ) separated by spaces. This means that line $\ell_i$ passes through the two points $P_i(a_i, b_i)$ and $Q_i(c_i, d_i)$ .

Output

Print the number of regions on a single line to standard output.

Hint

Examples1

Example 1
Input
```
4
0 4 6 4
0 0 6 6
1 0 1 6
0 6 6 0
```
Expected output
```
11
```