
几何题在 CSP-J/S 里出现得不算多,但一旦出现,往往需要把图形的位置关系翻译成向量运算。好消息是,竞赛里用的几何公式就那么几个,而且大多可以用整数运算避免精度问题。
本章的知识点与 GESP、CSP-J/S 大纲的对应关系如下。
| 考试 | 大纲要求 | 本章位置 |
|---|---|---|
| GESP C++ 八级 | 考点 5:代数与平面几何基础知识(初中数学部分) | 全章 |
| NOI 入门级 | 1.5.2 初等数学:代数(初中部分)、几何(初中部分) | 全章 |
坐标系与距离
平面上的点用坐标 (x, y) 表示。两点之间的欧几里得距离是
d = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}
在网格图里还有曼哈顿距离,只允许上下左右移动时的最短步数:
d = |x_1 - x_2| + |y_1 - y_2|
BFS 求无权图最短路得到的就是曼哈顿距离,这一点在《搜索算法》里会用到。
向量及其运算
把点 A 到点 B 的位移表示成向量 \vec{AB} = (x_B - x_A, y_B - y_A)。
点积
\vec{a} \cdot \vec{b} = x_1x_2 + y_1y_2 = |\vec{a}||\vec{b}|\cos\theta
用途:
- 判断垂直。点积为 0 说明两向量垂直。
- 求夹角余弦。
\cos\theta = \dfrac{\vec{a} \cdot \vec{b}}{|\vec{a}||\vec{b}|}。 - 判断方向。点积为正说明夹角是锐角,两个向量大致同向;为负说明是钝角。
叉积
二维叉积的结果是一个数:
\vec{a} \times \vec{b} = x_1y_2 - x_2y_1 = |\vec{a}||\vec{b}|\sin\theta
它有三种用法,都很好用。
一、判断方向。 \vec{a} \times \vec{b} > 0 说明从 \vec{a} 转到 \vec{b} 是逆时针,\vec{b} 在 \vec{a} 的左侧;小于 0 则相反;等于 0 说明两向量共线。
二、判断三点共线。 三点 A、B、C 共线,当且仅当 \vec{AB} \times \vec{AC} = 0。
三、计算面积。 以 \vec{a}、\vec{b} 为邻边的平行四边形面积是 |\vec{a} \times \vec{b}|,三角形面积是它的一半。
用坐标算叉积的代码:
struct Point {
long long x, y;
};
// 计算向量 AB 与 AC 的叉积
long long cross(Point a, Point b, Point c) {
return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}坐标是整数时,叉积的结果也是整数,不会引入任何浮点误差。这是竞赛几何里最喜欢用叉积的原因。
判断点和直线的位置关系
要判断点 C 在直线 AB 的哪一侧,算 \vec{AB} \times \vec{AC}:正数在一侧,负数在另一侧,零在直线上。
判断线段是否相交
两条线段相交,需要满足「跨立」条件:每条线段的两个端点分别在另一条线段所在直线的两侧(或者恰好在直线上)。
bool onSegment(Point p, Point a, Point b) { // p 在线段 ab 上
return cross(a, b, p) == 0 &&
min(a.x, b.x) <= p.x && p.x <= max(a.x, b.x) &&
min(a.y, b.y) <= p.y && p.y <= max(a.y, b.y);
}
bool intersect(Point a, Point b, Point c, Point d) {
long long d1 = cross(a, b, c);
long long d2 = cross(a, b, d);
long long d3 = cross(c, d, a);
long long d4 = cross(c, d, b);
bool opp12 = (d1 > 0 && d2 < 0) || (d1 < 0 && d2 > 0); // 严格异号
bool opp34 = (d3 > 0 && d4 < 0) || (d3 < 0 && d4 > 0);
if (opp12 && opp34) return true; // 严格跨立
if (d1 == 0 && onSegment(c, a, b)) return true; // 端点在另一条线段上
if (d2 == 0 && onSegment(d, a, b)) return true;
if (d3 == 0 && onSegment(a, c, d)) return true;
if (d4 == 0 && onSegment(b, c, d)) return true;
return false;
}多边形面积
三角形面积
三个点 A、B、C 围成的三角形面积是
S = \frac{|\vec{AB} \times \vec{AC}|}{2}
double triangleArea(Point a, Point b, Point c) {
return fabs((double)cross(a, b, c)) / 2.0;
}多边形面积:鞋带公式
顶点按顺序(顺时针或逆时针)给出的多边形,面积是
S = \frac{1}{2}\left| \sum_{i=1}^{n} (x_i y_{i+1} - x_{i+1} y_i) \right|
其中 x_{n+1} = x_1、y_{n+1} = y_1,也就是首尾相接。
double polygonArea(vector<Point> &p) {
long long s = 0;
int n = p.size();
for (int i = 0; i < n; i++) {
int j = (i + 1) % n;
s += p[i].x * p[j].y - p[j].x * p[i].y;
}
return fabs(s) / 2.0;
}公式名字来自它的计算方式,像系鞋带一样交叉相乘再相减。整数坐标下 s 是整数,最后一步才除以 2,所以能先精确算出两倍的面积。
精度处理
几何题里浮点数是绕不开的,因为开方和除法会产生无理数。几条原则:
- 能不用浮点就不用。 判断共线、判断方向、算面积这些,用叉积在整数下完成,精确且快。
- 比较大小用误差容限。 不要写
if (a == b),写成if (fabs(a - b) < EPS),EPS一般取10^{-9}。 - 输出按题目要求保留位数。 题目通常会说明保留几位小数,或者用 SPJ 按误差比对。
- 避免反复开方。 比较距离大小时,比较距离的平方即可,省一次开方也少一次误差。
const double EPS = 1e-9;
bool equal(double a, double b) { return fabs(a - b) < EPS; }
bool greaterThan(double a, double b) { return a - b > EPS; }
bool lessThan(double a, double b) { return b - a > EPS; }几个常用公式
点到直线的距离
点 P 到直线 AB 的距离,等于以 AB 为底、P 为顶点构成的三角形的高:
d = \frac{|\vec{AB} \times \vec{AP}|}{|\vec{AB}|}
分子是叉积(整数坐标下可以精确算),分母是 AB 的长度。这个式子就是「三角形面积 = 底 × 高 ÷ 2」的变形。
点到线段的距离
点到线段要分三种情况,不能直接套上面的公式:
- 投影落在
A的外侧,答案是|PA|; - 投影落在
B的外侧,答案是|PB|; - 投影落在
AB上,答案才是点到直线的距离。
完整的写法见后面的练习 3。
常见图形的面积与周长
| 图形 | 面积 | 周长 |
|---|---|---|
| 长方形 | a \times b |
2(a+b) |
| 正方形 | a^2 |
4a |
| 圆 | \pi r^2 |
2\pi r |
| 三角形 | \dfrac{1}{2} \times 底 \times 高 |
a+b+c |
圆里面的 \pi 在程序里一般写成 acos(-1.0),比手写 3.14159 精度高。
圆内与圆外
判断点 (x, y) 是否在以原点为圆心、半径为 r 的圆内,比较 x^2 + y^2 与 r^2 即可,不必开方。这样既快,又避开了开方带来的精度损失。
常见易错点
- 叉积的公式记反。是
x_1y_2 - x_2y_1,写成x_1y_1 - x_2y_2会得到错误结论。 - 判断三点共线用叉积等于 0,不要用斜率相等,后者在竖直方向会除零。
- 叉积的结果是两个乘积之差,坐标到
10^9时结果能到10^{18}量级,必须用long long。判断两个叉积是否异号时,写成(a > 0 && b < 0) || (a < 0 && b > 0),不要写成a * b < 0,两个10^{18}相乘会溢出long long。 - 鞋带公式要求顶点按顺序给出,顶点乱序会算出奇怪的面积。
- 浮点数直接用
==比较,几乎必然出错。 - 坐标是整数时不要过早转成
double,整数叉积更可靠。 - 点到线段的距离不能直接套点到直线的公式:投影落在线段的延长线上时,答案应该是两个端点到该点距离中的较小者。
初赛选择题精选
下面 8 道题中,题 16 选自 GESP 八级真题(几何类考点集中在 GESP 八级,CSP-J/S 第一轮里出现得不多),题 78 按本章考点编写。真题题干保持原样,选项做了重新编排。
题 1(GESP 八级,2026 年 6 月)
在平面直角坐标系中,三角形三个顶点为 A(1,1)、B(5,2)、C(3,6),该三角形的面积为( )。
A. 6 B. 9 C. 18 D. 36
答案:B
解析:\vec{AB} = (4, 1),\vec{AC} = (2, 5),叉积为 |4 \times 5 - 1 \times 2| = 18。叉积是平行四边形面积,三角形面积是它的一半,即 18 / 2 = 9。选 C 就是忘了除以 2,选 D 是把叉积本身当成了三角形面积的两倍。
题 2(GESP 八级,2023 年 12 月)
已知三个 double 类型的变量 a、b 和 theta 分别表示一个三角形的两条边长及二者的夹角(弧度),则下列哪个表达式可以计算这个三角形的面积?
A. a * b * sin(theta) / 2 B. (a + b) * sin(theta) / 2
C. a * b * cos(theta) / 2 D. sqrt(a * a + b * b - 2 * a * b * cos(theta))
答案:A
解析:两边及其夹角求面积用 S = \dfrac{1}{2}ab\sin C。D 是余弦定理,算的是第三条边,不是面积。
题 3(GESP 八级,2024 年 12 月)
已知两点 A(x_a, y_a)、B(x_b, y_b),假设直线 AB 的斜率存在,下列哪个表达式可以用来表示它?
A. (xa - xb) / (ya - yb) B. (ya - yb) / (xa - xb)
C. (ya - yb) * (xa - xb) D. (xa + xb) / (ya + yb)
答案:B
解析:斜率是「纵坐标之差除以横坐标之差」,即 k = \dfrac{y_a - y_b}{x_a - x_b}。A 把分子分母写反了,C 用乘法也是错的。题目特意加了「斜率存在」这个条件,就是在避开竖直方向。
题 4(GESP 八级,2024 年 3 月)
已知 int 类型的变量 a、b、c 中分别存储着一个三角形的三条边长,则这个三角形的面积可以由下列哪个表达式求得?
A. sqrt((a+b+c) * (b+c-a) * (a+c-b) * (a+b-c)) / 4
B. sqrt((a+b+c) * (b+c-a) * (a+c-b) * (a+b-c)) / 2
C. ((a+b+c) * (b+c-a) * (a+c-b) * (a+b-c)) / 4
D. sqrt(a * a + b * b - c * c) / 2
答案:A
解析:这就是海伦公式。设半周长 s = \dfrac{a+b+c}{2},面积 S = \sqrt{s(s-a)(s-b)(s-c)}。把 s 代进去通分,分母是 16,开方后就是 4,所以选 A。C 少了开方。
题 5(GESP 八级,2026 年 3 月)
已知三个点 A(x_1, y_1)、B(x_2, y_2)、C(x_3, y_3)。下列 C++ 表达式中,在精度误差 10^{-8} 内能正确判断这三点共线的是( )。
A. fabs((x2-x1)*(y3-y1) - (x3-x1)*(y2-y1)) < 1e-8
B. fabs((x2-x1)*(y3-y1) + (x3-x1)*(y2-y1)) < 1e-8
C. fabs((x2-x1)*(x3-x1) - (y2-y1)*(y3-y1)) < 1e-8
D. (y2-y1)/(x2-x1) == (y3-y1)/(x3-x1)
答案:A
解析:A 算的是 \vec{AB} \times \vec{AC},叉积为 0 就是共线。B 把减号写成了加号,C 把横纵坐标混在一起了,D 用斜率相等,碰到竖直线(x_2 = x_1)会除以零。
题 6(GESP 八级,2026 年 6 月)
判断点 (x, y) 是否在以原点为圆心、半径为 r 的圆内或圆上,下列做法最合适的是( )。
A. 计算 sqrt(x*x + y*y) 再和 r 比较
B. 比较 x*x + y*y 和 r*r
C. 比较 x + y 和 r
D. 分别比较 fabs(x)、fabs(y) 和 r
答案:B
解析:两边平方后比较,既避开了开方,也避开了开方带来的精度损失。A 虽然也能得到正确结果,但多做一次开方,且结果存在误差。
题 7(向量点积的几何意义)
已知向量 \vec{a} = (3, 4),\vec{b} = (1, 0),则 \vec{a} \cdot \vec{b} 的值为( )。
A. 3 B. 4 C. 5 D. 7
答案:A
解析:点积的坐标公式是 \vec{a} \cdot \vec{b} = x_1 x_2 + y_1 y_2 = 3 \times 1 + 4 \times 0 = 3。
几何意义:点积等于 |\vec{a}| |\vec{b}| \cos\theta,其中 |\vec{a}| = 5、|\vec{b}| = 1,所以 5 \times 1 \times \cos\theta = 3,得 \cos\theta = 0.6。这也说明 \vec{b} 是 x 轴方向,点积恰好等于 \vec{a} 在 x 轴上的投影长度 3。
选 C 是把 |\vec{a}| = \sqrt{3^2+4^2} = 5 当成了点积。
题 8(叉积判断方向)
已知 \vec{a} = (2, 3)、\vec{b} = (4, 6),则( )。
A. \vec{a} \times \vec{b} > 0,两向量夹角为锐角
B. \vec{a} \times \vec{b} = 0,两向量共线
C. \vec{a} \times \vec{b} < 0,两向量夹角为钝角
D. 无法判断
答案:B
解析:叉积 \vec{a} \times \vec{b} = x_1 y_2 - x_2 y_1 = 2 \times 6 - 4 \times 3 = 12 - 12 = 0。
叉积为 0 意味着什么? 叉积的绝对值是两向量张成的平行四边形面积,面积为 0 说明它们「张不出面积」,也就是共线(平行或反向)。这里 \vec{b} = 2\vec{a},确实共线。
叉积的符号意义:> 0 表示 \vec{b} 在 \vec{a} 的逆时针方向,< 0 表示顺时针。这是判断「点在直线的哪一侧」和「线段相交」的核心工具。
练习
练习 1:三角形面积
题目描述
给定三个点的坐标,求这三点围成的三角形面积,保留两位小数。保证三点不共线。
输入格式
一行六个整数 x_1、y_1、x_2、y_2、x_3、y_3,依次表示三个点的坐标。
输出格式
输出一个实数,表示三角形面积,保留两位小数。
数据范围
- 坐标的绝对值不超过
10^4,保证三点不共线。
输入输出样例
输入
0 0 4 0 0 3输出
6.00题目分析
直接用叉积公式:S = \dfrac{|\vec{AB} \times \vec{AC}|}{2}。叉积用整数算,最后一步才转成 double 除以 2,这样整个计算过程中没有精度损失。
参考代码
练习 2:多边形面积
题目描述
给定一个简单多边形的 n 个顶点坐标(按逆时针或顺时针顺序给出),求它的面积,保留一位小数。
输入格式
第一行一个整数 n;接下来 n 行,每行两个整数表示一个顶点坐标。
输出格式
输出一个实数,表示多边形面积,保留一位小数。
数据范围
3 \le n \le 1000,坐标绝对值不超过10^4。
输入输出样例
输入
4
0 0
4 0
4 3
0 3输出
12.0题目分析
鞋带公式。相邻顶点交叉相乘再相减,累加起来取绝对值,最后除以 2。
注意末尾要和第一个点相接,代码里用 (i + 1) % n 就能自动处理。累加量用 long long:n 个点、坐标到 10^4 时,累加值能到 10^{11} 量级。
参考代码
练习 3:点到线段的距离
题目描述
给定点 P 和线段 AB 的两端坐标,求 P 到线段 AB 的最短距离,保留两位小数。
输入格式
一行六个整数,依次为 P、A、B 的坐标。
输出格式
输出一个实数,表示最短距离,保留两位小数。
数据范围
- 坐标绝对值不超过
10^4。
输入输出样例
输入
2 3 0 0 4 0输出
3.00题目分析
分三种情况,关键是先求出投影参数 t:
t = \frac{\vec{AB} \cdot \vec{AP}}{|\vec{AB}|^2}
t \le 0:投影落在A外侧,答案是|PA|;t \ge 1:投影落在B外侧,答案是|PB|;- 否则投影在线段上,答案用面积法:
\dfrac{|\vec{AB} \times \vec{AP}|}{|\vec{AB}|}。
还要先把「A 与 B 重合」这个退化情况处理掉,否则分母为 0。
参考代码
练习 4(进阶):判断线段是否相交
题目描述
给定两条线段的四个端点坐标,判断它们是否相交(只要有一个公共点就算)。
输入格式
一行八个整数,依次为第一条线段的两个端点和第二条线段的两个端点坐标。
输出格式
相交输出 YES,否则输出 NO。
数据范围
- 坐标绝对值不超过
10^4。
输入输出样例
输入
0 0 1 1 0 1 1 0输出
YES题目分析
跨立实验。两条线段相交,要么满足「严格跨立」(每条线段的两个端点分别在另一条所在直线的两侧),要么有端点在另一条线段上。
两个细节:
- 判断「异号」要写成
(a > 0 && b < 0) || (a < 0 && b > 0),不能写成a * b < 0,两个10^{18}量级的叉积相乘会溢出。 - 叉积为 0 时还要确认那个点真的落在线段范围内,而不是落在延长线上,所以需要
onSeg。
参考代码
小结
平面几何在竞赛里的核心思路是:能用整数就不碰浮点,必须用浮点就统一用 EPS 比较。
- 两点距离用勾股定理,网格图上的最短步数是曼哈顿距离。
- 点积判断垂直和夹角,叉积判断方向、共线,还能算面积。
- 叉积的绝对值除以 2 是三角形面积,鞋带公式算多边形面积。
- 点到直线的距离用「两倍面积除以底」,点到线段还要判断投影落没落在线段上。
- 判断圆内外比较平方即可,不必开方。
学完这一章,下面这些事应该能独立完成:
- 写出叉积函数,并用它判断三点共线、判断点在直线的哪一侧。
- 用叉积求三角形面积,用鞋带公式求多边形面积。
- 写出点到线段的距离,并说清为什么要分三种情况。
- 写出跨立实验判断线段相交,并说清为什么不能写成
d1 * d2 < 0。 - 说清哪些几何判断可以用整数完成,哪些必须用
EPS。