На территории будущей стройки растут три дерева. Фирма получила разрешение на строительные работы с условием, что два (любых) дерева будут сохранены. Прораб хочет построить забор треугольной формы так, чтобы внутри него оказалось ровно два дерева.
Деревья на плане изображаются кругами, которые попарно не вложены друг в друга и не пересекаются (но могут касаться).
Напишите программу, которая по введенной информации о деревьях определит, возможно ли построить такой забор, и, если да, то какое дерево окажется не огорожено.
Вводится информация о трех деревьях: для каждого дерева координаты центра и радиус круга, изображающего это дерево на плане. Все числа целые, не превосходящие по модулю 3000. Радиус – натуральное число.
Выведите одно число – номер дерева (деревья нумеруются начиная с 1 в порядке задания их во входных данных), которое окажется не огорожено. Если забор треугольной формы, огораживающий ровно два дерева, построить невозможно, выведите число 0. Если существует несколько решений, выведите любое.
Как известно, к северу от Москвы находится много горнолыжных трасс, расположенных на холмах Клинско-Дмитровской гряды. Один из курортов в связи с финансовым кризисом решил расширить спектр услуг, предлагая трассы для катания не только на лыжах и сноубордах, но и санные трассы.
У хозяев курорта имеется топографическая карта территории, высоты на которой отображены с помощью контуров, каждый из которых представляет собой окружность. У каждой окружности указана высота поверхности, прилегающей к внутреннему контуру этой окружности. Вся территория, которая не находится внутри какой-либо окружности, имеет высоту 0. Поскольку это единственная информация о местности, то можно условно считать, что участки между окружностями плоские. Никакие две окружности не пересекаются и не касаются.
Используя эту карту, необходимо проложить санную трассу, которая будет удовлетворять двум условиям: разница высот между начальной и конечной точками должна быть максимальна, и количество пересекаемых контуров не должно превышать некоторого заданного значения \(K\) (это связано с тем, что то место, которым сидят на санках, имеет ограниченную прочность). При этом трасса может иметь участки подъема, но не должна включать в себя ни одной точки, которая была бы выше начальной (туда санки просто не заедут).
На приведенном рисунке пунктирной линией показана наилучшая трасса для \(K\) = 4. Разница высот в ней составляет 68.
Сначала вводятся два натуральных числа \(C\) (1 ≤ \(C\) ≤ 2 000) — количество окружностей и \(K\) (1 ≤ \(K\) ≤ 2 000) – максимальное количество окружностей, которое может пересечь трасса.
Далее идут описания окружностей, каждое из которых состоит из четырех целых чисел: \(X\), \(Y\) (–2000 ≤ \(X\) ≤ 2000, –2000 ≤ \(Y\) ≤ 2000) – координаты центра окружности, \(R\) (1 ≤ \(R\) ≤ 2000) — радиус окружности и \(A\) (–1000 ≤ \(A\) ≤ 1000) — высота местности, касающейся внутреннего края окружности.
Выведите одно число — максимальный перепад высот на трассе.
Пример
| Входные данные | Выходные данные |
| 10 4 38 61 2 73 69 34 3 15 61 59 4 30 40 60 5 66 58 44 6 30 71 34 6 -2 47 21 6 45 41 58 8 52 41 57 11 37 48 40 33 10 | 68 |