<PREV Problem:
NEXT>
Solved by 32 users: Jacob, MasterZerg, Ravent, mikleb, DD, tomek, dan, swistak, marek.cygan, maciejk, Rizvanov, crazyb0y, tourist, WsemirZ, JohnJones_001, Chmeli_BSU, DAV, zloy_mipt, mazahaka, RAVEman, defrager, Bogolubsky, fetetriste, TTLovePP, Yagi_Arthur, Dest, ripatti, Kuznetsov_S, Progger, LiuChenheng, regmar, NIGHTFIT.
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

Plane partition.

Time limit = 2 second(s)

You are given many line segments on a plane. Intersection of any two segments can be point or empty set. You have to determine how many "rooms" our plane is divided to.

Input First line contains number of line segments N, 0 < N ≤ 1000. Each of next N lines has four integers Х1, Y1, Х2, Y2 --- coordinates of line segment ends. Absolute values of coordinates does not exceed 100000.

Output Number of rooms.

Input#1
1 
1 1 2 2
Output#1
1

Input#2
4 
0 0 0 1 
0 1 1 1 
1 1 1 0 
1 0 0 0

Output#2
2

Author:
First Moscow Individual Programming Championship, 17 October 2004, MIPT

<PREV | Problem set | Search related messages | NEXT>


© acm.mipt DevGroup
The page was generated in 200ms

SW soft NIX
ID = 54.162.181.75