## 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 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 ≤ 10^{5}). Each of the next N lines

describes a different fence using four integers X0 , Y0 , X1 and Y1 (−10^{4} ≤ X0 , Y0 , X1 , Y1 ≤

10^{4} ). 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

-1Output:

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 |