eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Конусы

Конусы

Даны \textbf{n} конусов в пространстве. Никакие два конуса не имеют общих точек. Основания конусов лежат в одной плоскости, и сами конусы лежат по одну сторону от этой плоскости. Можно соединять вершины конусов отрезками, если и только если отрезок не имеет общих точек с конусами. \InputFile Первая строка содержит число \textbf{n} (1 ≤ \textbf{n} ≤ \textbf{300}). Далее, в \textbf{n} строках даны по четыре числа \textbf{x_i}, \textbf{y_i}, \textbf{r_i}, \textbf{h_i} --- координаты центра основания конуса, радиус основания, высота конуса. Все числа целые (\textbf{-500} ≤ \textbf{x_i}, \textbf{y_i} ≤ \textbf{500}, \textbf{1} ≤ \textbf{r_i} ≤ \textbf{100}, \textbf{1} ≤ \textbf{h_i} ≤ \textbf{100}). \OutputFile Выведите единственное целое число --- через какое наименьшее количество отрезков можно дойти до \textbf{n}-го конуса, если стартовать из первого.
Лимит времени 1 секунда
Лимит использования памяти 64 MiB
Входные данные #1
3
0 0 1 2
0 3 1 3
0 6 1 2
Выходные данные #1
2
Автор Станислав Пак
Источник Зимняя Школа, Харьков 2011