Задача №111776. Платные дороги
Мэр одного большого города решил ввести плату за проезд по шоссе, проходящим в районе города, чтобы снизить объем транзитного транспорта. В районе города проходит n шоссе.
Но руководство области, в которой расположен город, воспротивилось планам мэра. Действительно – дальнобойщики представляют собой неплохой источник доходов для большого количества кафе и гостиниц в небольших городках.
В результате решили, что плата будет введена только на шоссе, которые проходят через город.
В городе используется развитая система метрополитена, всего в городе есть m станций метро. Решено было, что шоссе проходит через город, если либо одна из станций метро расположена непосредственно на шоссе, либо есть хотя бы одна станция с каждой стороны от шоссе.
Помогите теперь мэру определить, какие шоссе проходят через город.
Первая строка входного файла содержит два целых числа: n и m – количество шоссе и количество станций метро, соответственно (1 ≤ n, m ≤ 100 000).
Следующие n строк описывают шоссе. Каждое шоссе описывается тремя целыми числами a, b и c и представляет собой прямую на плоскости, задаваемую уравнением a×x+b×y+c = 0 (|a|, |b|, |c| ≤ 106). Следующие m строк входного файла описывают станции метро. Каждая станция описывается двумя целыми числами x и y и представляет собой точку на плоскости с координатами (x, y) (|x|, |y| ≤ 106).
Первая строка выходного файла должна содержать одно целое число – количество шоссе, которые проходят через город. Вторая строка должна содержать номера этих шоссе в возрастающем порядке. Шоссе нумеруются от 1 до n в порядке, в котором они описаны во входном файле.
Система тестов состоит из двух групп:
В тестах первой группы выполняется ограничение \(n \le 10^4\). За прохождение этой группы ставится 50 баллов.
В тестах второй группы дополнительных ограничений нет. За прохождение этой группы ставится также 50 баллов.
4 2 0 1 0 1 0 1 1 1 0 1 1 -1 0 0 2 0
3 1 3 4