Problem C
Cake Cutting
It’s SoCCat’s birthday, and they have baked a delicious cake for the occasion. Unfortunately, there are too many students in SoC who is attending the party and interested in eating the cake. It is not feasible to cut the cake into sectors, otherwise the angle of each sector would be too small.
We model the cake on the Cartesian coordinate plane as a circle with radius $10000$ (in some unknown unit) with center $(0, 0)$. $N$ SoC students are invited to cut the cake, and each of them will be making a single straight cut. The $i$-th student will make a cut on the straight line from point $(x_ i, y_ i)$ to point $(x’_ i, y’_ i)$, where $(x_ i, y_ i)$ and $(x’_ i, y’_ i)$ are distinct points lying on the circumference of the circle.
Obviously, the cake will be divided into several pieces by the cuts. SoCCat wants to know the number of pieces that the cake will be divided into after all the cuts are made, in order to call the correct number of students to eat the cake.
Input
The first line of input contains an integer $N$ ($1 \leq N \leq 30$), the number of cuts by the students.
The next $N$ lines each contain four integers $x_ i$, $y_ i$, $x’_ i$, $y’_ i$ ($-10000 \leq x_ i, y_ i, x’_ i, y’_ i \leq 10000$), the coordinates of the two endpoints of the cut made by the $i$-th student.
It is guaranteed that the cuts are distinct, i.e. there are no two cuts which entirely overlap.
Output
Output a single integer, the number of pieces that the cake will be divided into after all the cuts are made.
| Sample Input 1 | Sample Output 1 |
|---|---|
2 10000 0 -10000 0 0 10000 0 -10000 |
4 |
| Sample Input 2 | Sample Output 2 |
|---|---|
3 8000 6000 -8000 -6000 10000 0 -10000 0 0 10000 0 -10000 |
6 |
