Runda 21 [Basic] - Cyrkiel

23.05.2011 - Damian Rusak
Trudność

 

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 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.

 

Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.
0
Twoja ocena: Brak

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com