Runda 20 - Wzór Picka

Zawody stałe, runda 20.

Limit czasowy: 1s ; Limit pamięciowy: 32 MB;

Wzór Pick'a

Sławek dziś na lekcji matematyki poznał wzór Picka. Powiedzmy, że w kartezjańskim układzie współrzędnych kropkami zaznaczymy wszystkie punkty o obu współrzędnych całkowitych. Kropki te nazwijmy punktami kratowymi (dlaczego kratowymi można łatwo zgadnąć rysując układ współrzędnych na kartce w kratkę). Jeśli teraz narysujemy wielokąt (wypukły lub wklęsły) o wierzchołkach w punktach kratowych i liczba punktów kratowych leżących wewnątrz wielokąta będzie wynosiła W, a liczba punktów kratowych leżących na brzegu B to pole wielokąta będzie równe:



(Spróbuj zastanowić się, jak można by udowodnić jego poprawność!) Na rysunku poniżej widać wielokąt o wierzchołkach w punktach kratowych. Ilość punktów kratowych wewnątrz tego wielokąta (kolor czerwony) wynosi 16. Ilość punktów kratowych leżących na brzegu wielokąta wynosi 26. Zatem pole figury - zgodnie z wzorem picka - wynosi czyli . Sławek zna też inny wzór na obliczenie pola takiej figury, ale nie przepada za iloczynami skalarnymi, więc wzór Picka bardzo mu się spodobał.

Sławek zastanawia się czy ten wzór na pewno jest poprawny. Dla małych wielokątów sprawdził ten wzór na kartce. Dla dużych wielokątów wolałby jednak użyć komputera. Pomożesz Sławkowi?

Napisz program, który dla danego wielokąta liczy liczbę punktów kratowych wewnątrz wielokąta oraz na jego brzegu.

Wejście:

Na standardowym wejściu znajduje się liczba () oznaczające liczbę wierzchołków wielokąta. W kolejnych liniach znajdują się współrzędne oraz () kolejnych wierzchołków wielokąta.

Wyjście:

W jedynej linii standardowego wyjścia należy wypisać dwie liczby całkowite B oraz W oznaczające liczbę punktów kratowych znajdujących się na brzegu wielokąta, oraz liczbę punktów kratowych leżących w jego wnętrzu.

Dla danych wejściowych (rysunek z przykładu):

10
1 1
9 1
11 5
7 4
9 7
6 4
6 3
5 6
1 10
5 2

Poprawną odpowiedzią jest:

26 16