Polygon Lattice Points

题目描述

给定一个多边形，你的任务是计算多边形内部和其边界上的格点数。格点是坐标为整数的点。 多边形由 n 个顶点 $(x_1,y_1),(x_2,y_2),\dots,(x_n,y_n)$ 组成。对于 $i=1,2,\dots,n-1$，顶点 $(x_i,y_i)$ 和 $(x_{i+1},y_{i+1})$ 是相邻的，且顶点 $(x_1,y_1)$ 和 $(x_n,y_n)$ 也是相邻的。

输入格式

第一行输入一个整数 n：顶点的个数。 接下来有 n 行描述这些顶点。第 i 行有两个整数 $x_i$ 和 $y_i$。 你可以假设该多边形是简单的，即不自交。

输出格式

输出两个整数：多边形内部的格点数和其边界上的格点数。

4
1 1
5 3
3 5
1 4

6 8

提示

$3 \le n \le 10^5$ $-10^9 \le x_i, y_i \le 10^9$

标签: CSES2193|几何

来源

CSES2193|几何