JARA - Jara’s Legacy

no tags 

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 is 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 mini-
mum 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

hide comments
Ordan Santos: 2017-10-22 17:13:42

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.


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