算法:皮克定理 + 最大公约数
时间复杂度:$O(1)$
皮克定理 百度百科
具体为 $S = a + \frac{b}{2} - 1$,其中 $a$ 为三角形内部点的数量,$b$ 为三角形边上点的数量,$S$ 为三角形的面积。
$S = \frac{p \times m}{2}$,关键在于求解 $b$。
先将每条边移至 $(0, 0)$ 点处,具体的将一条边的两个顶点对应横纵坐标相减即可得到新的坐标值 $(x, y)$,则斜率为 $\frac{y}{x}$,约分得到 $\frac{y’}{x’}$,则求满足 $\frac{y’}{x’} = \frac{d}{c}(0 < d \le y,0 < c \le x)$,则 $\frac{y’}{x’} = \frac{m \times d}{m \times c} (1 \le m \le gcd(y,x))$,$m$ 取值为整数,此时的 $b$ 就等于 $x$ 和 $y$ 的最大公约数即 $gcd(x, y)$。
注意:求 $gcd(y, x)$ 需要加绝对值,因为可能移至第二或第四象限。
C++ 代码
#include <iostream>
#include <algorithm>
using namespace std;
#define x first
#define y second
typedef pair<int, int> PII;
const int N = 12;
int n, m, p;
PII q[N];
int main()
{
cin >> n >> m >> p;
int s = m * p, b = 0;
q[1] = {0, 0}, q[2] = {n, m}, q[3] = {p, 0};
b += abs(__gcd(q[1].x - q[2].x, q[1].y - q[2].y));
b += abs(__gcd(q[1].x - q[3].x, q[1].y - q[3].y));
b += abs(__gcd(q[2].x - q[3].x, q[2].y - q[3].y));
cout << (s - b + 2) / 2 << endl;
return 0;
}