Задача Y. Гиперпрыжок

Автор:А. Щуров   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:512 Мб
Выходной файл:Стандартный выход  

Условие

Космический корабль собирается выполнить прыжок в гиперпространство. Прыжок будут снимать для документального фильма, поэтому нужно сделать его эффектным. Для этого режиссер поручил вам найти астероидное облако, сквозь которое корабль должен пролететь. Вы успешно с этим справились, и теперь съемочной группе нужно найти подходящее для взлета место.

В силу конструктивных особенностей летательного аппарата, он может производить взлет только с оси OX под углом 45, образуя острый угол между прямой траекторией взлета и положительным направлением OX.

Астероидное облако представляет собой N астероидов на плоскости, каждый из которых имеет форму круга радиусом ri и располагается в координате xi yi.

Для эффектного и безопасного взлета нужно подобрать подходящий коридор между астероидами, здесь-то и нужна ваша помощь! Вам нужно найти все коридоры ненулевой ширины в астероидном облаке. Каждый коридор представляет собой полосу, ограниченную сверху и снизу прямыми, наклон которых к оси OX составляет 45, такую, что её ширина максимально возможна, а на самой полосе нет частей астероидов. Шириной коридора считается расстояние между ограничивающими его прямыми.

Формат входных данных

Входные данные содержат два целое число N и затем N троек целых чисел xi yi ri.

Формат выходных данных

Выходные данные должны содержать количество коридоров и затем, в порядке возрастания, ширину каждого из них с точностью до трех знаков после запятой.

Ограничения

2 ≤ N ≤ 105

0 ≤ |xi|, yi ≤ 105,

1 ≤ ri ≤ 103

ri < yi

Примеры тестов

Стандартный вход Стандартный выход
1
2
4 2 1
2 4 1
1
0.828427

0.069s 0.024s 13