Internet Problem Solving Contest

IPSC 2000

Problem B – Cake

Some time ago a VERY huge cake was made in the village called Nalomena Trieska. Well, it was infinitely large and infinitely thin. For our needs it looked exactly like an infinite plane. It was not very tasty, so nobody wanted to eat it. Instead, local children started to play with it. Each of them drew one straight line on the plane. These lines divided the plane into many parts. For a few hours the children were happy, they jumped from one part into another and played other similar games. But then little Tommy suddenly asked: "How many parts does the cake have?" "1999." answered Martin. "No, 2000 !" replied Richard. "Well, I think it's only 1748." stated Michael. And they started to argue. Now their parents need your help, because the children spend all their time counting the parts of the cake.

Input file specification

The first line of the input file contains the number of straight lines N. Each of the next N lines contains four integers x1,y1,x2,y2 (the absolute value of each number is at most 10000). These integers are the coordinates of two different points in the plane [x1,y1] and [x2,y2]. These two points determine one straight line in the plane. You can assume that no two straight lines are the same.

Output file specification

The output file contains a single integer giving the number of parts into which given N lines divide the plane.


Input file:
5 0 0 5
4 0 4 5
2 4 3 4
1 1 1 5
Output file: