Hide

Problem H
Hoarse Horses

/problems/hoarsehorses/file/statement/en/img-0001.jpg
Picture by Alistair Hamilton via Flickr.

Farmer Bob’s horses all are hoarse and may have a cold – even the pony is a little hoarse! Because of that, all the farm animals need to be individually quarantined. To separate the animals, Farmer Bob has a set of $n$ fences that cannot be crossed. Unfortunately, Farmer Alice has taken all of Farmer Bob’s fences and placed them arbitrarily in the plane! Farmer Bob has no time to rearrange these fences – he must leave them as is.

Help Farmer Bob calculate how many of his prized barnyard animals he can quarantine. That is, Farmer Bob wants to place as many animals inside non-empty regions enclosed by the fences, such that no animal can reach another animal, and no animal can escape to infinity.

Each fence is given by a line segment between two points. It is given that no three fences go through the same point. Fences are allowed to cross each other.

Input

  • A single integer $1 \leq n \leq 1000$, the number of fences.

  • Then $n$ lines follow, each with four integers $-{10}^9 \leq x_1, y_1, x_2, y_2 \leq {10}^9$. These are the endpoints of the fences, each fence is given by a straight line segment between two endpoints.

Output

Output a single line containing a single integer $c$, the maximum number of animals Farmer Bob can quarantine.

\includegraphics[width=.4\textwidth ]{./sample-testcase3.pdf}
Figure 1: Illustration of the third example input.
Sample Input 1 Sample Output 1
1
1 1 1 2
0
Sample Input 2 Sample Output 2
4
1 0 1 5
4 0 4 5
0 1 5 1
0 4 5 4
1
Sample Input 3 Sample Output 3
5
1 0 1 5
4 0 4 5
0 1 5 1
0 4 5 4
-1 0 5 5
4

Please log in to submit a solution to this problem

Log in