Олимпиады по информатике (ХМАО - Югра)

   
 
Югорский НИИ ИТ, Югорский ФМЛ
Логин:   Пароль:    
 
   
 
Новости
О проекте
Регистрация
Гостевая книга
Форум
Архив задач
Состояние системы
Олимпиады
Работа в системе
Рейтинг
Новичкам
Методическое пособие
Дистанционное обучение
Дистрибутивы
Ссылки

















Праздничный торт

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

На дне рождения Пети на стол подали круглый торт, украшенный разноцветными розочками. Причем, на торте было ровно по две небольших розочки каждого цвета, а различных цветов было ровно K. Тем самым, общее число розочек было равно 2*K.

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

При этом оказалось, что:

  • никакие три разреза не прошли через одну точку,
  • никакие два разреза не совпали и не оказались параллельными.

Напишите программу, которая по заданному радиусу торта, и координатам розочек определяет, на сколько частей был разделен торт.

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

В первой строке входного файла INPUT.TXT содержатся два числа: действительное число R (радиус торта) и целое число K – количество различных цветов (1 ≤ K ≤ 100). В каждой из последующих K строк записано по четыре числа, разделенных пробелами: X1, Y1, X2, Y2 – координаты двух розочек каждого цвета. Центр торта находится в начале координат. Радиус торта и координаты розочек – действительные числа, не превышающие по абсолютной величине 100 и содержащие не более 6 цифр после запятой.

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

В выходной файл OUTPUT.TXT выведите целое число – количество частей, на которые был разрезан торт.

Примеры

INPUT.TXTOUTPUT.TXT
13 1
-1 -1 1 1
2
25 3
1 4 1 -3
-3.5 0 4 1.5
-3 3 0 -4
6

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

[Все попытки] [Лучшие попытки]


 
     
Югорский НИИ ИТ, Югорский ФМЛ