Generał kontra gawiedź

Limit pamięci: 128 MB

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.

Wejście

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.

Wyjście

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.

Przykład

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.