Runda 21 [Basic] - Cyrkiel

23.05.2011 - Damian Rusak

Zadanie tygodnia

runda 21; kategoria Basic

Limit czasowy: 1s; Limit pamięciowy: 32MB

Cyrkiel

Twój przyjaciel zadał Ci pewną zagadkę:

"Wyobraźmy sobie, że mamy na płaszczyźnie $n$ okręgów, takich, że żaden z nich nie zawiera w środku początku układu współrzędnych. Wbijamy jedną nóźkę cyrkla w środek układu współrzędnych i rysujemy nasz okrąg o pewnym promieniu $R$ - kosztuje nas to dokładnie $R$ (liczymy w jakiejś uniwersalnej walucie). Za każdy narysowany okrąg, z którym nasz okrąg przecina się w dwóch punktach otrzymujemy $5$ , za każdy, który nasz okrąg zawiera w sobie całkowicie (środek danego okręgu jest w naszym okręgu i oba mogą się stykać lecz nie przecinać) otrzymujemy $10$ .

Jak dobrać $R$ tak, aby zarobić jak najwięcej? Zarabiamy sumę nagród za przecinanie i zawieranie okręgów pomniejszoną o koszt promienia $R$ ".

Oczywiście nie możesz doczekać się rozwiązania - czy nie najłatwiej napisać program?

Wejście:

Pierwsza linia wejścia zawiera jedną liczbę całkowitą $n$ - liczbę okręgów narysowanych na płaszczyźnie. ( $1 \leq n \leq 10^5$ ) Kolejne $n$ linii zawiera trójki liczb $x_{i}$ $y_{i}$ oraz $r_{i}$ - odpowiednio współrzędne środka okręgu oraz jego promień. ( $-10^4 \leq x_{i}, y_{i}, r_{i} \leq 10 ^{4}$ ).

Wyjście:

Wyjście powinno składać się z jednej liczby, podanej z dokładnością do 2 miejsc po przecinku - największego zarobku możliwego do uzyskania.

Przykład:

Wejście:

2 2 1

-5 6 5

Wyjście:

11.17

Objaśnienie: Optymalny promień to $2*\sqrt{2} + 1$ - pokrywamy wtedy w pełni pierwszy okrąg i przecinamy się z drugim, dostając $15$ minus wielkość promienia. Nie opłaca się jednak pokrywać całego drugiego okręgu.