CSES2193 多边形的格点数
#CS2193. 多边形的格点数
多边形的格点数
题目背景
翻译自 CSES-2193 题。
题目描述
给定一个多边形，计算多边形内部和边界上的格点数。格点是指坐标为整数的点。
这个多边形有 n 个顶点 (x1,y1),(x2,y2),…,(xn,yn)(x_1, y_1), (x_2, y_2), \dots, (x_n, y_n)(x1,y1),(x2,y2),…,(xn,yn)。对于每个 i=1,2,…,n−1i = 1, 2, \dots, n-1i=1,2,…,n−1，顶点 (xi,yi)(x_i, y_i)(xi,yi) 和 (xi+1,yi+1)(x_{i+1}, y_{i+1}) (xi+1,yi+1) 是相邻的，而顶点 (x1,y1)(x_1, y_1)(x1,y1) 和 (xn,yn)(x_n, y_n)(xn,yn) 也是相邻的。
输入格式
第一行输入一个整数 n：表示多边形的顶点数。
接下来的 n 行，每行包含两个整数 xi x_i xi 和 yi y_i yi，表示多边形的第 i i i 个顶点的坐标。
假设多边形是简单的，即不会自交。
输出格式
输出两个整数，分别是多边形内部和边界上的格点数。
样例
4
1 1
5 3
3 5
1 4
6 8
说明/提示
−109≤xi,yi≤109-10^9 \leq x_i,y_i \leq 10^9−109≤xi,yi≤109。