Poligon
Limit pamięci: 64 MB
Armia Bajtocka planuje przeprowadzić wspólnie z Armią Bitocką wielkie manewry wojskowe.
Manewry odbędą się na poligonie w Bajtowie Pomorskim.
Poligon jest oficerom dobrze znany, jednak nie wiedzą oni dokładnie, jakie zadania
przyjdzie im wypełniać.
Dlatego właśnie zwrócili się do Ciebie, rekrucie, z "uprzejmą" prośbą.
Twoi przełożeni znają dokładny rozkład obiektów strategicznych znajdujących się na poligonie.
W czasie manewrów wielokrotnie będą musieli atakować różne obszary poligonu.
W szczególności, jedną z kluczowych decyzji będzie właściwe dobranie wielkości sił
przeznaczonych do ataku - siły te powinny być adekwatne do potrzeb, czyli
proporcjonalne do liczby obiektów strategicznych we wnętrzu atakowanego obszaru.
Twoim zadaniem będzie określenie dla każdego obszaru, reprezentowanego jako
wielokąt o wierzchołkach w obiektach strategicznych, ile obiektów
strategicznych znajduje się ściśle wewnątrz niego.
Wejście
W pierwszym wierszu standardowego wejścia znajdują się dwie liczby całkowite:
(), oznaczająca liczbę obiektów znajdujących się na poligonie,
oraz (), oznaczająca liczbę zapytań.
Obiekty są ponumerowane od do .
W kolejnych wierszach znajduje się par liczb całkowitych
(), oznaczających współrzędne -tego obiektu.
Żadne trzy obiekty nie leżą na jednej prostej.
W kolejnych wierszach znajduje się opisów zapytań.
Każdy taki opis rozpoczyna się od liczby określającej liczbę wierzchołków
wielokąta ().
Dalej następuje różnych liczb całkowitych
z przedziału oznaczających numery
obiektów strategicznych będących kolejnymi wierzchołkami wielokąta.
Żaden z podanych wielokątów nie będzie miał samoprzecięć, a wierzchołki wielokątów będą
podane zgodnie z kierunkiem ruchu wskazówek zegara.
Suma wszystkich liczb nie przekroczy .
Wyjście
Twój program powinien wypisać na standardowe wyjście wierszy zawierających
odpowiedzi na kolejne zapytania.
Odpowiedzią dla jednego zapytania jest liczba obiektów strategicznych znajdujących
się wewnątrz podanego wielokąta.
Przykład
Dla danych wejściowych:
6 4
0 0
0 5
5 0
11 10
5 5
2 1
4 1 2 4 3
4 1 2 5 3
3 6 2 4
3 1 2 6
poprawną odpowiedzią jest:
2
1
1
0
Kółka na rysunku reprezentują obiekty strategiczne, a liczby przy kółkach - ich numery.
Na rysunku zaznaczono obszary z pierwszego (linie ciągłe) i trzeciego (linie przerywane,
zamalowany na żółto) zapytania.
Autor zadania: Michał Pilipczuk.