Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

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

(Время: 3 сек. Память: 16 Мб Сложность: 59%)

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

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

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

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

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

В первой строке входного файла заданы два целых числа R, K (1 ≤ R < K ≤ 103). Во второй строке записано целое число N (0 ≤ N ≤ 105) количество волос в модели человека. В следующих N строках находится по 4 вещественных числа Xh, Yh, Xs, Ys – координаты начала и конца очередного волоса. Первая пара чисел соответствует концу, лежащему на окружности головы, вторая пара соответствует концу, лежащему на плечах.

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

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

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

Примеры

INPUT.TXTOUTPUT.TXT
11 2
3
0 -1 -2 -2
1 0 2 -2
-1 0 -1 -2
1
21 10
3
-1 0 -1 -10
0 -1 0 -10
1 0 1 -10
0

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

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

Красноярский краевой Дворец пионеров, (c)2006 - 2020, E-mail: admin@acmp.ru