<ПРЕД Задача:
СЛЕД>
Задачу решили 20 пользователей: mikleb, MasterZerg, dragonghy, dan, ignat, Cheryl, mishik, Ravent, Rizvanov, DAV, tourist, liulz, defrager, UdH-WiNGeR, zloy_mipt, RAVEman, mazahaka, Dest, Jacob, LiuChenheng.
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

Полуплоскости I

Time limit = 2 секунд(ы)

Дано множество замкнутых (включающих свою границу) полуплоскостей.

Выберите несколько из них, покрывающих всю плоскость. Их число должно быть минимальным.

Если же объединение всех данных полуплоскостей не покрывает плоскость, выведите точку, не принадлежащую ни одной из полуплоскостей.

Вход. В первой строке дано количество полуплоскостей N ( 0 < N ≤ 100 ). Затем идут N строк, в каждой из которых задана полуплоскость. Полуплоскость задается двумя точками (x1,y1), (x2,y2), лежащими на её границе. Полуплоскость находится слева от вектора (x1,y1) → (x2,y2).

Выход. Выведите количество полуплоскостей, а затем укажите их номера во входных данных (нумерация начинается с 1). Если набора полуплоскостей, покарывающих всю плоскость, нет, то выведите "-1", а в следующей строке выведите координаты точки, которая не лежит ни в одной полуплоскости.

Вход#1
2
3.14 2.718 18 49
18 49 3.14 2.718
Выход#1
2 
1 2

Вход#2
2
6 2 2 4
4 3 3 3.5
Выход#2
-1 
6.000000 2.000100
Вход#3
3
1 2 -1 1
2 3 3 6
-2 -1 1 -4
Выход#3
3 
1 2 3

Автор:
Евгений Барский, Владимир Челноков, Дмитрий Полищук, Андрей Локоть.

<ПРЕД | Вернуться к списку задач | Искать сообщения в форуме | СЛЕД>


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

SW soft NIX
ID = 3.235.172.213