初中代数几何在算法中的应用

---

初中代数几何在算法中的应用 (Math Toolbox)

教学目标：

1. 会用数列求和公式（等差 / 等比 / 平方和）做计数与复杂度估算。
2. 掌握一元二次方程求根与韦达定理，会用判别式判根。
3. 记住常用恒等式（平方差、完全平方、立方和差）用于化简。
4. 会用两点距离、三角形面积、叉积处理坐标几何，叉积能判方向 / 算面积 / 判点在线段哪侧。

前置：初中代数与平面几何、06.数组（一维与二维）、整数与浮点。

---

一、数列求和：计数与复杂度的常客

数列	求和公式	在算法里干嘛
等差 $1+2+\cdots +n$	$\frac{n(n+1)}{2}$	双重循环 $\sum i$ 的次数、选两个的对数 $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$
一般等差 $a_1+\cdots +a_n$	$\frac{n(a_1+a_n)}{2}$	区间和
等比 $1+r+\cdots +r^{n-1}$	$\frac{r^n-1}{r-1}$	满二叉树节点数 $2^h-1$、倍增
平方和 $1^2+\cdots +n^2$	$\frac{n(n+1)(2n+1)}{6}$	嵌套循环次数、某些计数

典型用途：估复杂度。形如 for i: for j<i 的循环跑了 ${\sum }_{i=1}^n(i-1)=\frac{n(n-1)}{2}=O(n^2)$ 次——这就是”两重循环是 $O(n^2)$“的来历。
也用于避免暴力：要算 $1+2+\cdots +n$，直接套 $\frac{n(n+1)}{2}$ 是 $O(1)$，不必循环。注意 $n$ 大时乘积要用 long long（$n=10^5$ 时 $n^2\approx 10^{10}$ 已爆 int）。

---

二、一元二次方程与韦达定理

方程 $a{x}^2+bx+c=0(a\ne 0)$：

• 判别式 $\Delta =b^2-4ac$：$\Delta >0$ 两不等实根，$\Delta =0$ 一个，$\Delta <0$ 无实根。
• 求根公式 $x=\frac{-b\pm \sqrt{\Delta }}{2a}$。
• 韦达定理（根与系数）：$x_1+x_2=-\frac{b}{a}$，$x_1{x}_2=\frac{c}{a}$。

在算法里：解”和为 $S$、积为 $P$ 的两个数”直接套韦达（它们是 $x^2-Sx+P=0$ 的根）；二分 / 数学题里判”是否存在整数解”先看 $\Delta$ 是否为完全平方数。浮点开根 sqrt 有误差，要整数解时记得四舍五入后回代验证。

---

三、常用恒等式（化简利器）

$$(a\pm b{)}^2=a^2\pm 2ab+b^2,a^2-b^2=(a+b)(a-b)$$ $$a^3\pm b^3=(a\pm b)(a^2\mp ab+b^2),(a+b)(a-b)=a^2-b^2$$

用途：把式子化简成好算的形式。例如判断 $a^2-b^2$ 是否为某数，分解成 $(a+b)(a-b)$ 后枚举因子，比枚举 $a,b$ 快得多；平方差也常用于”两数之差 × 两数之和”的计数题。

---

四、平面几何与坐标几何

4.1 距离、中点、面积

• 两点 $A(x_1,y_1)$、$B(x_2,y_2)$ 的距离：$\sqrt{(x_1-x_2{)}^2+(y_1-y_2{)}^2}$。

  比较距离大小时比较距离的平方即可，避免开根的浮点误差、还能用整数。

• 中点：$\left(\frac{x_1+x_2}{2},\frac{y_1+y_2}{2}\right)$。
• 勾股定理：直角三角形 $a^2+b^2=c^2$；判直角、算斜边。
• 三角形面积：$\frac{底\times 高}{2}$；已知三边用海伦公式 $S=\sqrt{p(p-a)(p-b)(p-c)}$，$p=\frac{a+b+c}{2}$。

4.2 叉积：计算几何的地基

向量 $\vec{u}=(x_1,y_1)$、$\vec{v}=(x_2,y_2)$ 的叉积（一个数）：

$$\vec{u}\times \vec{v}=x_1{y}_2-x_2{y}_1$$

它一招三用，全是整数运算、无浮点误差：

看叉积符号	含义
$>0$	$\vec{v}$ 在 $\vec{u}$ 逆时针方向（左转）
$<0$	$\vec{v}$ 在 $\vec{u}$ 顺时针方向（右转）
$=0$	两向量共线（平行）

long long cross(long long ax, long long ay, long long bx, long long by) {
    return ax * by - ay * bx;          // 叉积，注意 long long 防溢出
}
// 判点 C 在有向线段 A->B 的哪一侧：看 cross(B-A, C-A) 的符号
long long side(long long ax,long long ay,long long bx,long long by,long long cx,long long cy){
    return cross(bx-ax, by-ay, cx-ax, cy-ay);   // >0 左侧, <0 右侧, =0 共线
}

用途：三角形 $ABC$ 面积 $=\frac{|\text{cross}(B-A,C-A)|}{2}$；判三点是否共线（叉积为 0）；判转向（凸包、判点在多边形内都靠它）。这是后续计算几何的第一块砖。

---

小结

• 求和公式：等差 $\frac{n(n+1)}{2}$、平方和 $\frac{n(n+1)(2n+1)}{6}$——用于计数与复杂度估算，大数用 long long。
• 一元二次：判别式 $\Delta =b^2-4ac$、求根公式、韦达 $x_1+x_2=-\frac{b}{a},x_1{x}_2=\frac{c}{a}$；要整数解先判 $\Delta$ 是否完全平方。
• 恒等式：平方差 $a^2-b^2=(a+b)(a-b)$ 等用于化简 / 因子枚举。
• 坐标几何：比距离用距离平方；叉积 $x_1{y}_2-x_2{y}_1$ 一招判方向 / 算面积 / 判共线，全程整数无误差。

练习

• 用公式 $O(1)$ 求 $1^2+2^2+\cdots +n^2$，与循环结果对拍。
• 给三个点的坐标，用叉积判它们是否共线、并求三角形面积（面积可能是半整数，输出 $\times 2$ 的整数）。
• 已知两数之和与之积，用韦达 / 求根判是否为两个整数。

这些是 GESP / CSP 初赛数学题的高频考点，也是后续二分答案、计数、计算几何的底座。