POLSKI SPOJ

Z woli króla Maciusia ma powstać pierwszy w Bajtlandii park etnograficzny. W tym celu ogłoszono konkurs na projekt takiego parku. Konkurs okazał się sporym sukcesem i tylko niektóre projekty, spośród wielu nadesłanych, zostaną wybrane do dalszej fazy konkursu.

Zdecydowano, że w fazie wstępnej projekty zostaną poddane ocenie parametrycznej, w której jednym z elementów jest koszt utworzenia i utrzymania parku, a który z kolei zależy od długości ogrodzenia, jakie trzeba będzie wokół niego wybudować. Ponieważ obiekty, które będą umieszczone w Parku mają nieregularne kształty, a ponadto konieczne jest zagwarantowanie wolnej przestrzeni parku wokół każdego obiektu, ustalono, że dobrym przybliżeniem będzie plan, na którym obiekty będą zaznaczone jako okręgi. Twoim zadaniem jest dla każdego planu oszacowanie najmniejszej możliwej długości ogrodzenia budowanego w taki sposób, aby park stanowił jeden spójny obszar.

Wejście

W pierwszej linii liczba testów t. Dla każdego testu w pierwszej linii liczba okręgów n i w kolejnych liniach dla każdego okręgu trzy liczby całkowite -1000 ≤ x ≤ 1000, -1000 ≤ y ≤ 1000, 1 ≤ r ≤ 1000, współrzędne środka i promień okręgu odpowiednio. Nie należy zakładać, że okręgi się nie przecinają lub, że nie są położone jeden wewnątrz drugiego.

Wyjście

Dla każdego testu w oddzielnej linii jedna liczba będąca minimalną długością ogrodzenia wokół parku.

Punktacja

Niech l_i oznacza wzorcową długość otoczki, a l_i^' długość obliczoną przez program dla planu o numerze i.

Niech ε_i =|(l_i-l_i^')/l_i| i x_i=1.1 + 0.14 log ε_i, gdzie log oznacza logarytm dziesiętny. Wartości wzorcowe podawane są z dokładnością do 1e-10.

Punktacja za ocenę planu o numerze i wynosi: p_i=1-min(1, max(0, x_i))

Ostatecznie liczba punktów za zadanie składające się z t testów wynosi:

score=10(p₁+ p₂ + ... + p_t)/t

zadanie uważa się za rozwiązane, jeśli score > 2.

Przykład

Wejście:
1
2
100 100 100
500 100 100

Komentarz

Wzorcowa odpowiedź w tym przypadku, to 1428,3185307180

Dla odpowiedzi 1428,215 punktacja w zaokrągleniu do 1e-2 wynosi 4,54.

Testy przykładowe

Dwa przykładowe zestawy danych z rozwiązaniami (zip).