旋转矩形整点计数问题：解析CodeSignal题解的数学原理

问题描述 #

在笛卡尔平面上有一边长为偶数a、b的矩形，中心与原点(0,0)重合，边与坐标轴成45度角，求其内部（含边界）的整数坐标点数量。

已知JavaScript解法 #

function solution(a, b) {
    var pointsA = Math.floor(Math.sqrt(a * a / 2)),
        pointsB = Math.floor(Math.sqrt(b * b / 2));
    return (pointsA * pointsB + Math.floor((pointsA + pointsB) / 2)) * 2 + 1;
}

解法原理解析 #

1. 坐标变换简化问题 #

因为矩形与坐标轴成45度角，直接分析原坐标系的点会很繁琐，我们做45度旋转的坐标变换：
令 u = x + y，v = x - y。
此时原斜置矩形会变成平行于u、v轴的轴对齐矩形，其边界条件转化为：
$$|u| \leq \frac{a}{\sqrt{2}}, \quad |v| \leq \frac{b}{\sqrt{2}}$$

2. 整数坐标的对应条件 #

原坐标(x,y)是整数，当且仅当u和v同奇偶：
因为 $x = \frac{u+v}{2}$，$y = \frac{u-v}{2}$，只有u+v和u-v都是偶数（即u、v同奇或同偶）时，x、y才会是整数。

3. 确定u、v的整数范围 #

代码中的pointsA = Math.floor(Math.sqrt(a²/2))，而$\sqrt{a²/2} = \frac{a}{\sqrt{2}}$，所以pointsA是满足$|u| \leq \frac{a}{\sqrt{2}}$的最大整数u；同理pointsB是满足$|v| \leq \frac{b}{\sqrt{2}}$的最大整数v。

4. 统计符合条件的(u,v)对 #

我们需要统计满足$|u| \leq pointsA$、$|v| \leq pointsB$且u、v同奇偶的(u,v)对数，这就是原问题要求的整数点数量。

通过分情况推导（记A=pointsA，B=pointsB）：

• 当A、B均为偶数：同奇偶对数为$2AB + A + B + 1$
• 当A偶、B奇或A奇、B偶：同奇偶对数为$2AB + A + B$
• 当A、B均为奇数：同奇偶对数为$2AB + A + B + 1$

而代码中的公式(A*B + Math.floor((A+B)/2))*2 +1可以统一覆盖这四种情况：

• 若A+B为偶数（A、B同奇偶）：$\text{floor}((A+B)/2) = (A+B)/2$，代入得$2AB + A+B +1$
• 若A+B为奇数（A、B异奇偶）：$\text{floor}((A+B)/2) = (A+B-1)/2$，代入得$2AB + A+B$

这个结果正好等于所有符合条件的整数(x,y)的数量。

内容的提问来源于stack exchange，提问作者Minh Long Vu