In the event of technical difficulties with Szkopuł, please contact us via email at [email protected].
If you are familiar with IRC chat, the support team is also reachable on PIRC network (irc.pirc.pl
) in #szkopul
channel. If you are not, just use email.
Please do not ask us things like "how to solve task XYZ?".
Please remember that the support team has to sleep sometimes or go to work in real life.
W Bajtogrodzie niesamowite poruszenie! Bajtoccy archeolodzy odkryli w pobliżu miasta szczątki dinozaurów. Gdy tylko gawiedź się o tym zwiedziała, ten i ów jął wybierać się na wykopalisko po to, by zwędzić mniejszą lub większą kość. Proceder ten stał się tak nagminny, że postanowiono do ochrony terenu wykopalisk zatrudnić wojsko.
Generał Bajtazar rozlokował żołnierzy
w strategicznych punktach na terenie wykopalisk.
(Żołnierze nie mogą stanąć gdzie bądź, aby nie przeszkadzać
archeologom. Poza tym muszą mieć też dobrą widoczność, aby
chronić teren wykopalisk.)
Powiemy, że dany punkt terenu jest chroniony, jeśli
ruszając się z niego w jakimkolwiek kierunku, zbliżymy się do któregoś z żołnierzy
(tj. nasza odległość od tego żołnierza zmaleje).
Bajtazarowi przydzielono właśnie
nowego rekruta. Generał może go umieścić w jednym z
jeszcze nieobsadzonych punktów strategicznych.
Dla każdego z tych punktów interesuje go, jaka będzie
powierzchnia chronionego terenu, gdy nowy żołnierz
stanie w tym punkcie.
W pierwszym wierszu wejścia znajdują się dwie liczby całkowite
i
(
,
),
oznaczające liczbę rozstawionych żołnierzy i liczbę
nieobsadzonych punktów strategicznych.
Kolejne
wierszy opisuje żołnierzy: w
-tym
z tych wierszy znajdują się liczby całkowite
(
), które oznaczają współrzędne punktu
(w prostokątnym układzie współrzędnych),
w którym stoi
-ty żołnierz.
W kolejnych
wierszach zapisane są w tym samym formacie
kolejne nieobsadzone punkty strategiczne.
Punkty podane na wejściu nie powtarzają się.
Można założyć, że powierzchnia terenu chronionego przez już rozstawionych żołnierzy jest dodatnia.
Na wyjście należy wypisać dokładnie wierszy. W
-tym wierszu
należy wypisać całkowitą powierzchnię chronionego terenu, jeśli nowy rekrut
stanie w
-tym nieobsadzonym punkcie strategicznym.
Liczby należy wypisywać z dokładnie jedną cyfrą po kropce dziesiętnej.
Dla danych wejściowych:
3 2 0 0 2 -1 1 2 3 1 1 0
poprawną odpowiedzią jest:
5.0 2.5
Autor zadania: Tomasz Idziaszek.