Серьёзного человека Ларри, преподавателя квантовой физики в университете
Миннесоты, в последнее время преследуют неудачи. Ларри узнал,
что жена хочет разорить его, дочь ворует у него деньги на пластическую операцию, у сына
проблемы в школе, а руководство факультета получает анонимные письма,
очерняющие его.
Но это ещё не всё. Полиция только что арестовала Артура, брата Ларри,
несколько месяцев жившего в его доме и круглыми сутками работавшего
над загадочной книгой «Ментакулус».
Когда Ларри решил почитать «Ментакулус», оказалось, что
книга представляла собой собрание рисунков
сумасшедшего — все страницы были испещрены причудливыми геометрическими фигурами.
На одной из страниц Ларри увидел множество точек и дуг окружностей. На мгновение
ему показалось, что эти точки и дуги образуют ухмыляющиеся рожицы.
Неужели в душе Артура не было светлых чувств и вся она была наполнена
лишь сарказмом? Ларри решил посчитать, сколько ухмыляющихся
рожиц изображено на странице. Для этого, как настоящий учёный, он ввёл строгое
определение — дуга окружности PQR и пара точек A и B образуют
рожицу, если выполняются следующие условия:
- точки A и B лежат по другую сторону от прямой PR, нежели точка Q;
- углы APR, ARP, BPR, BRP — острые;
- расстояние от точек A и B до прямой PR меньше удвоенной длины отрезка PR;
- прямая AB не имеет общих точек с отрезком PR.
Помогите Ларри посчитать, сколько рожиц изображено на рисунке.
Исходные данные
В первой строке записаны целые числа n и m (1 ≤ n ≤ 100; 1 ≤ m ≤ 10000) —
количество дуг и количество точек соответственно. В каждой из следующих n строк
описывается очередная дуга — записаны координаты трёх точек в том
порядке, в котором они расположены на дуге. Величины всех дуг не превосходят 180 градусов.
Гарантируется, что три точки, задающие дугу, попарно различны и не
лежат на одной прямой. В следующих m строках записаны координаты точек.
Все координаты целые и не превосходят 10000 по абсолютному значению.
Все дуги и все точки попарно различны.
Результат
Выведите количество ухмыляющихся рожиц на странице «Ментакулуса».
Пример
исходные данные | результат |
---|
2 7
-2 2 0 0 2 2
-2 -2 0 0 2 -2
-1 3
1 3
0 5
0 3
-1 -3
1 -3
2 -3
| 4
|
Автор задачи: Алексей Самсонов (подготовка — Виктор Камашев)
Источник задачи: XV Открытый чемпионат Урала по спортивному программированию (апрель, 2011)