Голова на плечах

Изготовитель всемирно известного шампуня, компания «Голова на плечах» всерьез заботится о качестве своей продукции. В частности, она постоянно улучшает различные показатели своего шампуня, с целью чего постоянно проводит исследования. Но, согласно законодательству, на человеке проводить исследования нельзя, а проводить исследования на животных компания считает ниже своего достоинства. Поэтому ученые, работающие в компании, разработали математическую модель человека и проводят исследования на ней.

Человек, согласно этой модели, состоит из головы и плеч. Голова представляет собой окружность с центром в точке (0,0) и радиусом R, а плечи бесконечную прямую y = −K, где R < K.

Объектом изучения исследователей являются волосы. Каждый волос в данной модели представлен отрезком, начинающимся на голове (строго на окружности) и заканчивающимся на плечах (строго на прямой). При этом ни один волос не имеет с окружностью головы более одной общей точки. В данный момент ученые озабочены проблемой секущихся волос. Пара волос называется секущейся, если соответствующие этим волосам отрезки имеют общую точку.

Дана математическая модель человека. Найдите количество секущихся пар волос.

Входные данные

В первой строке входного файла заданы два целых числа R, K (1 ≤ R < K ≤ 10³). Во второй строке записано целое число N (0 ≤ N ≤ 10⁵) количество волос в модели человека. В следующих N строках находится по 4 вещественных числа X_h, Y_h, X_s, Y_s – координаты начала и конца очередного волоса. Первая пара чисел соответствует концу, лежащему на окружности головы, вторая пара соответствует концу, лежащему на плечах.

Гарантируется, что никакой волос не имеет с окружностью головы более одной общей точки. Также гарантируется, что среди начальных и конечных точек нет одинаковых.

Выходные данные

В выходной файл OUTPUT.TXT выведите число секущихся пар волос.

Примеры

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]