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
Rizvanov`23 jan 2008`C++2200.59766
Rizvanov`23 jan 2008`C++2300.59766
Cheryl`21 sep 2007`C++100.02962
Jacob`06 dec 2010`C++200.071047
UdH-WiNGeR`28 mar 2009`Java4200.291161
liulz`13 oct 2008`C++200.291179
ignat`14 aug 2007`C++1100.161193
dan`13 may 2007`C++2000.341202
ignat`14 aug 2007`C++1000.161212
ignat`14 aug 2007`C++900.161224
mishik`05 oct 2007`C++1500.371250
dragonghy`16 apr 2007`FPC401.001423
Ravent`12 jan 2008`C++1100.161483
 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'.

 © acm.mipt DevGroupThe page was generated in 200ms