<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.
UserDateAttemptTimeCMSC
Rizvanov23 jan 2008C++2200.59766 
Rizvanov23 jan 2008C++2300.59766 
Cheryl21 sep 2007C++100.02962 
Jacob06 dec 2010C++200.071047 
UdH-WiNGeR28 mar 2009Java4200.291161 
liulz13 oct 2008C++200.291179 
ignat14 aug 2007C++1100.161193 
dan13 may 2007C++2000.341202 
ignat14 aug 2007C++1000.161212 
ignat14 aug 2007C++900.161224 
mishik05 oct 2007C++1500.371250 
dragonghy16 apr 2007FPC401.001423 
Ravent12 jan 2008C++1100.161483 
Languages
C++
16
Kylix
2
Java
1
FPC
1
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 

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 190ms

SW soft NIX
ID = 3.228.220.31