Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

ETNOPARK - Parki Etnograficzne

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 li oznacza wzorcową długość otoczki, a li' długość obliczoną przez program dla planu o numerze i.

Niech εi =|(li-li')/li| i xi=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: pi=1-min(1, max(0, xi))

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

score=10(p1+ p2 + ... + pt)/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.

Wskazówki

W prostszej wersji rozwiązania można zastąpić każdy okrąg wielokątem wypukłym do niego zbliżonym. Następnie znaleźć długość otoczki wypukłej (ang. convex hull) zawierającej wszystkie wierzchołki wszystkich wielokątów. Znalezioną długość traktować jako rozwiązanie.

Dokładne rozwiązanie można uzyskać postępując podobnie jak w algorytmie Jarvisa (ang. Gift wrapping algorithm lub inaczej Jarvis march). Do tego prawdopodobnie konieczne jest wyznaczanie zewnętrznych stycznych do dwóch okręgów (ang. Circle - Circle Tangents), zobacz więcej na ten temat w: MathWorld z lub w Cut the knot.

Testy są podzielone na 8 zestawów danych. Programy są testowane na każdym zestawie oddzielnie, za rozwiązanie każdego zestawu można otrzymać maksymalnie 1.25 punktu. Co drugi zestaw zawiera tylko małe okręgi dość oddalone od siebie. Dopuszczalne n zmienia się od kilku do kilku tysięcy w zależności od zestawu (każdy kolejny zestaw zawiera więcej danych).

Testy przykładowe

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


Dodane przez:kuszi
Data dodania:2007-05-14
Limit czasu wykonania programu:1s-4s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: GOSU
Pochodzenie:Projektowanie i Analiza Algorytmów 2007
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.