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

Конуси

Конуси

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

Дано n конусів у просторі. Ніякі два конуси не мають спільних точок. Основи конусів лежать в одній площині, а самі конуси лежать по одну сторону від цієї площини. Можна з'єднувати вершини конусів відрізками, якщо і лише якщо відрізок не має спільних точок з конусами.

Вхідні дані

Перший рядок містить число n (1 ≤ n300). Далі, в n рядках задано по чотири числа x_i, y_i, r_i, h_i — координати центра основи конуса, радіус основи, висота конуса. Всі числа цілі (-500x_i, y_i500, 1r_i100, 1h_i100).

Вихідні дані

Виведіть єдине ціле число — через яку найменшу кількість відрізків можна дійти до n-го конуса, якщо стартувати з першого.

Приклад

Вхідні дані #1
3
0 0 1 2
0 3 1 3
0 6 1 2
Вихідні дані #1
2
Автор Станіслав Пак
Джерело Зимова Школа, Харків 2011