Окружающие круги
Дано множество окружностей C с различными радиусами, расположенных в разных местах, возможно, пересекающихся. Также дана окружность с радиусом r, которую можно разместить так, чтобы она охватывала все окружности из множества C, если r достаточно велик.
Может быть несколько возможных положений окружности радиуса r, чтобы охватить все окружности из множества C. Обозначим область U как объединение областей всех таких охватывающих окружностей. Иными словами, для каждой точки в U существует окружность радиуса r, которая охватывает эту точку и все элементы множества C. Ваша задача — вычислить длину периметра этой области U.
Рисунок 1. демонстрирует пример множества окружностей C и области U. На рисунке три окружности из C изображены сплошными линиями, некоторые возможные положения охватывающих окружностей показаны пунктирными линиями, а область U обозначена толстой пунктирной замкнутой кривой.
Рисунок 1. Пример множества окружностей
Входные данные
Входные данные состоят из последовательности наборов данных. Количество наборов данных меньше 100.
Каждый набор данных имеет следующий формат.
n rx_1 y_1 r_1x_2 y_2 r_2...x_n y_n r_n
Первая строка набора данных содержит два положительных целых числа, n и r, разделенные пробелом. n — это количество окружностей в множестве C и не превышает 100. r — это радиус охватывающей окружности и не превышает 1000.
Каждая из следующих n строк содержит три целых числа, разделенных пробелом. (x_i, y_i) — это координаты центра i-й окружности из множества C, а r_i — ее радиус.
Можно предположить, что -500 ≤ x_i ≤ 500, -500 ≤ y_i ≤ 500, и 1 ≤ r_i ≤ 500.
Конец ввода обозначается строкой, содержащей два нуля, разделенные пробелом.
Выходные данные
Для каждого набора данных выведите строку с десятичной дробью, представляющей длину периметра (длину окружности) области U.
Погрешность вывода не должна превышать 0.01. Можно предположить, что при изменении r на ϵ (|ϵ| < 0.0000001), длина периметра области U изменится не более чем на 0.001.
Если r слишком мал, чтобы охватить все окружности в C, выведите строку, содержащую только 0.0.
В выводе не должно быть других символов.
Рисунок 2. Последний набор данных из примера ввода