| Codeforces Round 284 (Div. 1) |
|---|
| Закончено |
Сумасшедший город представляет собой плоскость, на которой имеется n бесконечных прямых дорог. Каждая дорога задаётся уравнением aix + biy + ci = 0, где ai и bi не равны нулю одновременно. Дороги разбивают плоскость на связные области, возможно бесконечной площади. Каждую такую область назовем кварталом. Перекрестком будем называть точку пересечения хотя бы двух различных дорог.
Ваш дом расположен в одном из кварталов. Сегодня вам надо добраться до университета, также расположенного в некотором квартале. За один шаг вы можете переместиться из одного квартала в другой, если протяжённость их общей границы ненулевая (в частности это значит, что если кварталы смежны одному перекрёстку, но не имеют общего ненулевого отрезка границы, то перейти из одного в другой за один шаг нельзя).
Определите, какое минимальное количество шагов вам придётся сделать, чтобы оказаться в квартале, содержащем университет. Гарантируется, что ни ваш дом, ни университет не расположены на дороге.
В первой строке записано два целых чисел через пробел x1, y1 ( - 106 ≤ x1, y1 ≤ 106) — координаты вашего дома.
Во второй строке записано два целых числа через пробел x2, y2 ( - 106 ≤ x2, y2 ≤ 106) — координаты университета, где вы учитесь.
В третьей строке записано целое число n (1 ≤ n ≤ 300) — количество дорог в городе. В следующих n строках записаны через пробел по 3 целых числа ( - 106 ≤ ai, bi, ci ≤ 106; |ai| + |bi| > 0) — коэффициенты прямой aix + biy + ci = 0, задающей i-ю дорогу. Гарантируется, что никакие две дороги не совпадают. Кроме этого, ни ваш дом, ни университет не лежат на дороге (т. е. не принадлежат ни одной из прямых).
В единственной строке выведите одно целое число — ответ на задачу.
1 1
-1 -1
2
0 1 0
1 0 0
2
1 1
-1 -1
3
1 0 0
0 1 0
1 1 -3
2
Рисунки к примерам представлены ниже (A — точка, соответствующая дому; B — точка, соответсвующая университету; разными цветами обозначены области, соответствующие разным кварталам):
