ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Чемпионат Урала 2011

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

J. Ментакулус

Ограничение времени: 3.0 секунды
Ограничение памяти: 64 МБ
Серьёзного человека Ларри, преподавателя квантовой физики в университете Миннесоты, в последнее время преследуют неудачи. Ларри узнал, что жена хочет разорить его, дочь ворует у него деньги на пластическую операцию, у сына проблемы в школе, а руководство факультета получает анонимные письма, очерняющие его.
Но это ещё не всё. Полиция только что арестовала Артура, брата Ларри, несколько месяцев жившего в его доме и круглыми сутками работавшего над загадочной книгой «Ментакулус». Когда Ларри решил почитать «Ментакулус», оказалось, что книга представляла собой собрание рисунков сумасшедшего — все страницы были испещрены причудливыми геометрическими фигурами.
На одной из страниц Ларри увидел множество точек и дуг окружностей. На мгновение ему показалось, что эти точки и дуги образуют ухмыляющиеся рожицы. Неужели в душе Артура не было светлых чувств и вся она была наполнена лишь сарказмом? Ларри решил посчитать, сколько ухмыляющихся рожиц изображено на странице. Для этого, как настоящий учёный, он ввёл строгое определение — дуга окружности PQR и пара точек A и B образуют рожицу, если выполняются следующие условия:
  1. точки A и B лежат по другую сторону от прямой PR, нежели точка Q;
  2. углы APR, ARP, BPR, BRP — острые;
  3. расстояние от точек A и B до прямой PR меньше удвоенной длины отрезка PR;
  4. прямая 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)
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1839. Ментакулус