Počítání mřížových bodů

Mřížový bod je každý bod roviny, který má obě souřadnice celočíselné. V této úloze je dán (ne nutně konvexní) mnohoúhelník v rovině s vrcholy v mřížových bodech a vaším úkolem je spočítat, kolik mřížových bodů v něm leží. Počítáme přitom i mřížové body ležící na obvodu mnohoúhelníka.

Nějaké body dostanete, pokud vyřešíte variantu úlohy, kde je mnohoúhelník konvexní, nebo variantu, kde nás zajímá jen počet mřížových bodů na obvodu mnohoúhelníka.

Mohou se vám také hodit nějaké myšlenky z úlohy o počítání obsahu mnohoúhelníka. Naopak není potřeba používat věty o mřížových bodech. Pokud nějakou znáte, můžete ji použít jen tehdy, pokud ji také dovedete dokázat.