Sesja

Napisać program, który sprawdzi czy punkt P o podanych współrzędnych należy do wnętrza dowolnego n-kąta zbudowanego z n wierzchołków.

Wejście:

Na wejściu podajemy liczbę całkowitą dodatnią m < 10000, będącą liczbą powtórzeń serii danych. W kolejnych wierszach wczytujemy współrzędne (x,y) punktu P, rozdzielone znakiem nowej linii, liczbę całkowitą dodatnią 0 < n < 1000 par liczb całkowitych -10000 < x, y < 10000 oddzielonych spacją, oznaczających współrzędne wierzchołków wielokąta o n kątach.

Wyjście:

Na wyjściu w osobnych wierszach dostajemy komunikat 'Tak', gdy punkt P należy do wnętrza wielokąta lub 'Nie' w przeciwnym wypadku, będący odpowiedzią na każdy przypadek testowy.

Przykład
Wejście:
2
3
6
5
1 1
7 6
2 10
1 6
-2 8
5
10
5
1 1
7 6
2 10
1 6
-6 9

Wyjście:
Tak
Nie

Wskazówka:
Zastosować algorytm geometryczny sprawdzający czy dwa odcinki się przecinają (Iloczyn wektorowy). 
Punkt należy do wnętrza figury złożonej z n odcinków, gdy prosta przechodząca przez ten punkt przecina boki n-kąta nieparzystą liczbę razy.