JARA - Jara’s Legacy

Victor Jara was a Chilean teacher, theater director and political activist. He is widely recognized because of his talent as poet and song writer. His most recognized work is probably the song “A Desalambrar” that can be translated from Spanish as “Unwire”. In this song Jara assures that people are the rightful owner of the lands, and so wire fences that delimit private properties should be cut down to allow access to everybody. Although Jara’s proposal is far from being fulfilled, some of his convinced listeners keep trying to make it happen. Since they must face several enemies, they try to make their job efficient by only cutting down the necessary number of fences and not more.

Each fence can be modeled as a segment (straight line) connecting two points in the XY plane. These endpoints are considered to be part of the fence. A cut in a fence removes any contiguous part of the fence except the endpoints. An area is said to be free if and only if, for any pair of points not lying over a fence, there is a (not necessarily straight) line that connect these points without crossing any fence. Given the location of the fences, your job is to calculate the minimum number of fences that need to be cut down to make the area free, according to the above definition.

Input

Each test case is described using several lines. The first line contains an integer N indicating the number of fences in the area (1 ≤ N ≤ 105).

Each of the next N lines describes a different fence using four integers X0, Y0, X1 and Y1 (−104 ≤ X0, Y0, X1, Y1 ≤ 104). These values represent that there is a fence whose endpoints in the XY plane are (X0, Y0) and (X1, Y1). You may assume that for each fence its two endpoints are distinct. Besides, within each test case, the intersection of any pair of fences is either empty or it is an endpoint of both fences. The end of input is indicated with a line containing a single −1.

Output

For each test case, output a single line containing a single integer representing the minimum number of fences that need to be cut down to make the area free.

Example

Input:
9
-50 0 0 0
0 0 50 0
-50 0 0 50
0 50 50 0
-50 0 0 -50
0 -50 50 0
0 0 0 -50
0 -50 50 -50
50 -50 50 0
2
0 1 2 3
0 0 2 2
-1

Output:
4
0

Added by:Pablo Ariel Heiber
Date:2010-09-27
Time limit:4.548s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 NODEJS OBJC VB.NET
Resource:FCEyN UBA ICPC Selection 2010

hide comments
2017-10-22 17:13:42 Ordan Santos
I wonder why there is duplicate fences in the input and why each duplicate increase the answer by one. It took me a long time to figure out that.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.