Вчений кіт
"Край Прибережжя дуб зелений,
І золотий ланцюг на нім,
І день, і ніч там кіт учений -
По ланцюгу кружляє тім..."
Від’їжджаючи з домівки, поет залишав коту, прикутому до дуба ланцюгом довжиною L, N рибин. Знаючи координати голови та хвоста кожної з них, порахуйте, на яку добу у кота виникне почуття голоду, якщо він починає голодувати тоді, коли за добу з'їсть менше, ніж K рибин. Рибину він може з'їсти, якщо зможе дотягнутись хоча б до однієї її точки. Координати дуба (0, 0).
Технічні умови
Вхідні дані
У першому рядку знаходяться L, N, K. Далі йде N рядків: координати голови (X1i, Y1i) та хвоста (X2i, Y2i) кожної з рибин. Всі вхідні дані - цілі числа, що не перевищують за модулем 100.
Вихідні дані
Єдине число - день, на який у кота з'явиться відчуття голоду.
Інформація про задачу
Ліміт часу: 1 секундаЛіміт пам`яті: 64 MB
Бали за пройдений тест: 8.33333
Складність: 47% 95/180
Автор: Присяжнюк А.В
Класифікація: Геометрія
Приклад
Приклад вхідних даних4 4 2 1 1 -1 3 2 2 4 2 -3 -4 -3 4 1 -5 4 -4 |
Приклад вихідних даних2 |
| ← Червоні та сині квадрати | Список задач | Розрізане число → |