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

MWP4_1B - Anteny

Warszawska Wyższa Szkoła Informatyki planuje od nowego semestru zimowego uruchomić pierwszą na świecie stację radiową przeznaczoną dla wąskiej grupy społecznej jaką stanowią informatycy. Audycje poświęcone będą zagadnieniom związanym z sieciami komputerowymi, programowaniem oraz z innymi niezwykle ekscytującymi tematami. Znamy już nawet tytuł jednego z quizów: "Jaki to algorytm?".

Jak to na ogół bywa w świecie informatyki nic nie może być tak proste jak mogłoby się wydawać. Autorzy projektu stanęli przed niezwykle trudnym zadaniem - wyborem anteny. Wybór anteny jest o tyle krytyczną decyzją, iż w zależności od jej rodzaju emituje różnej długości fale a co za tym idzie sygnał dociera na różne odległości. Na posiedzeniu rady projektu podjęto wydawać by się mogło nieco szokującą decyzję – otóż postanowiono zakupić wszystkie dostępne rodzaje anten i nadawać fale o różnych długościach! Rada projektu założyła przy tym, że każdy słuchacz nastawi odbiornik na możliwie najkrótsze dla niego fale. Twoim zadaniem jest określenie na podstawie zasięgu poszczególnych nadajników i współrzędnych odbiorców, ilu słuchaczy będzie korzystać z danej anteny oraz ilu znajdzie się całkowicie poza zasięgiem rozgłośni. Zakładamy, że wszystkie anteny znajdują się w punkcie o współrzędnych (0,0) - im mniejszy zasięg nadajnika, tym krótsze fale emituje. Warto także zaznaczyć, że przy jednym odbiorniku może siedzieć kilku odbiorców wtedy ich współrzędne będą się pokrywały.

Wejście

W pierwszej linii wejścia znajduje się dokładnie jedna liczba całkowita Z (1 ≤ Z ≤ 3) określająca liczbę zestawów danych.

Każdy zestaw w pierwszej linii zawiera jedną liczbę całkowitą m (1 ≤ m ≤ 1000) określającą liczbę anten. W drugiej linii znajduje się m posortowanych rosnąco liczb - każda z nich opisuje zasięg kolejnej zakupionej anteny. W trzeciej linii zestawu danych znajduje się liczba całkowita z (1 ≤ z ≤ 600000) – jest to liczba słuchaczy. W kolejnych z liniach następuje opis każdego z słuchaczy, składający się z jego współrzędne x, y (-10000 ≤ x, y ≤ 10000; x ≠ 0 lub y ≠ 0).

Wyjście

Dla każdego zestawu danych należy w oddzielnych liniach wypisać liczbę słuchaczy dla każdej z anten, w kolejności zgodnej z kolejnością nadajników na wejściu. W ostatniej linii wyjścia każdego zestawu należy wypisać liczbę odbiorców nie objętych zasięgiem żadnej anteny.

Przykład

Wejście:

1
2
3 7
9
2 1
-1 -1
0 3
4 3
-5 -2
-7 0
10 10
1 0
2 1

Wyjście:

5
3
1

Dodane przez:Maciej Boniecki
Data dodania:2012-03-13
Limit czasu wykonania programu:0.100s-1s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM64 GOSU
Pochodzenie:IV Mistrzostwa WWSI w Programowaniu
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.