eolymp
bolt
Try our new interface for solving problems
Məsələlər

Покрытие

Покрытие

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB

Пользователь сотового телефона перемещается вдоль отрезка с концами, имеющими целочисленные координаты. Для того чтобы он смог пользоваться сотовым телефоном, последний должен быть в пределах радиуса передачи некоторой башни. По мере того как пользователь передвигается по пути, сотовая связь может быть получена (или утрачена) вследствие перемещения внутрь радиуса действия некоторой башни (или вне радиуса действия всех башен). Учитывая местоположение до 100 вышек и их радиусов действия, Вы должны рассчитать процент покрытия сотового телефона, которым обладает пользователь на указанном пути. Координаты (x, y) представляют собой целые числа от -100 до 100 включительно, а радиусы башни - целые числа от 1 до 100 включительно.

Giriş verilənləri

Каждая строка содержит один тест в формате: n c0x c0y c1x c1y t1x t1y t1r t2x t2y t2r ... Здесь n - количество башен, (c0x, c0y) - начальная точка движения пользователя телефона, (c1x, c1y) - конечная точка, (tkx, tky) - положение k-ой башни, а tkr - ее радиус передачи. Начальная и конечная точки пути различны. Последнаяя строка содержит 0.

Çıxış verilənləri

Для каждой конфигурации выведите одну строку, содержащую процент покрытия сотового телефона, округленный до двух десятичных знаков.

Nümunə

Giriş verilənləri #1
3 0 0 100 0 0 0 10 5 0 10 15 0 10
1 0 0 100 0 40 10 50
0
Çıxış verilənləri #1
25.00
88.99
Mənbə 2009 ACM North America - Rocky Mountain, Задача B