<PREV Problem:
NEXT>
Solved by 20 users: mikleb, MasterZerg, dragonghy, dan, ignat, Cheryl, mishik, Ravent, Rizvanov, DAV, tourist, liulz, defrager, UdH-WiNGeR, zloy_mipt, RAVEman, mazahaka, Dest, Jacob, LiuChenheng.
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

Half-planes I

Time limit = 2 second(s)

You are given set of closed half planes.

You have to determine minimum subset that covers the whole plane.

If its impossible, you have to find point that does not belongs to any of given half planes.

Input. The first line contains number N of half planes, 0 < N ≤ 100. Each of next N lines contains half plane description. Each half plane description is four numbers --- coordinates of two points (x1,y1), (x2,y2) on its border. Half plane is on the left side of the vector (x1,y1) → (x2,y2).

Output. Print minimum number of half planes and their order numbers.

If there is point not belonging to any of given half planes, then output -1 and coordinates of the point.

Input#1
2
3.14 2.718 18 49
18 49 3.14 2.718
Output#1
2 
1 2

Input#2
2
6 2 2 4
4 3 3 3.5
Output#2
-1 
6.000000 2.000100
Input#3
3
1 2 -1 1
2 3 3 6
-2 -1 1 -4
Output#3
3 
1 2 3

Author:
Eugene Barsky, Vladimir Chelnokov, Dmitry Poleshuk, Andrey Lokot'.

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


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

SW soft NIX
ID = 23.20.13.165