Runda 20 - Wzór Picka

15.02.2010 - Krzysztof Piecuch
TrudnośćTrudność

 

 

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:

$ P = W + B/2 - 1 $

(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 $ 16 + 26/2 - 1 $ czyli $ 28 $. 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 $ N $ ($ 3 \leq N \leq 1000000 $) oznaczające liczbę wierzchołków wielokąta. W kolejnych liniach znajdują się współrzędne $ x $ oraz $ y $ ($ -2000 \leq x, y \leq 2000 $) 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

Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.
PozycjaImię i nazwiskoWynikCzas
1Przemysław Derengowski1004:34:54
2Bartek Dudek1010:14:38
3Michal Zgliczynski1010:37:48
4Anna Piekarska1051:34:31
5Miłosz Łakomy10178:49:58
6Grzegorz Milka10464:53:49
7Mateusz Wasilewski10538:02:44
8Szymon Stankiewicz107190:27:25
9Krzysztof Pszeniczny108078:23:52
10Marek Rusinowski108171:19:25
11Anna Szybalska109206:31:41
12Mateusz Twaróg109251:22:35
5
Twoja ocena: Brak Ocena: 5 (1 ocena)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com