二维几何基础
向量运算
向量 , ：
- 点积：
- 叉积：
叉积符号判断方向： 则 在 逆时针方向。
struct Point {
double x, y;
Point(double x = 0, double y = 0) : x(x), y(y) {}
Point operator+(const Point &p) const { return {x + p.x, y + p.y}; }
Point operator-(const Point &p) const { return {x - p.x, y - p.y}; }
double dot(const Point &p) const { return x * p.x + y * p.y; }
double cross(const Point &p) const { return x * p.y - y * p.x; }
};叉积符号与转向
叉积的符号直接反映两个向量的转向关系：
- ： 在 的 左侧（逆时针），即左转
- ： 在 的 右侧（顺时针），即右转
- ：两向量共线
给定三点 ，通过 判断转向：
int ccw(Point a, Point b, Point c) {
double t = (b - a).cross(c - a);
if (t > eps) return 1; // 左转（逆时针）
if (t < -eps) return -1; // 右转（顺时针）
return 0; // 共线
}叉积符号是所有几何判定（线段相交、凸包、点与多边形关系）的基础。
!
!
线段相交
快速排斥实验 + 跨立实验：
bool segInter(Point a, Point b, Point c, Point d) {
if (max(a.x, b.x) < min(c.x, d.x) || max(c.x, d.x) < min(a.x, b.x)) return 0;
if (max(a.y, b.y) < min(c.y, d.y) || max(c.y, d.y) < min(a.y, b.y)) return 0;
double c1 = (b - a).cross(c - a), c2 = (b - a).cross(d - a);
double c3 = (d - c).cross(a - c), c4 = (d - c).cross(b - c);
return c1 * c2 <= 0 && c3 * c4 <= 0;
}快速排斥实验：先判断两线段包围盒是否相交，排除明显不相交的情况。
跨立实验：利用叉积判断每条线段的两个端点是否在另一条线段的两侧。 分别表示 相对于 的方位， 分别表示 相对于 的方位。
当 且 时，两线段相交（包括端点重合的情况）。
!
点在多边形内
光线投射法：从点引射线，统计与多边形边交点个数，奇内偶外。
bool pointInPoly(Point p, vector<Point> &poly) {
int n = poly.size(), cnt = 0;
for (int i = 0; i < n; ++i) {
Point a = poly[i], b = poly[(i + 1) % n];
if (segInter(p, {1e9, p.y + 1}, a, b)) cnt++;
}
return cnt & 1;
}多边形面积
利用叉积求有向面积（鞋带公式）：
double polygonArea(vector<Point> &p) {
double s = 0;
for (int i = 0; i < (int)p.size(); ++i)
s += p[i].cross(p[(i + 1) % p.size()]);
return fabs(s) / 2;
}| 题目 | 说明 |
|---|---|
| P1153 点和直线 | 点、直线操作 |
| P1355 平面几何 | 点、线综合 |
| 路径D-DSA算法刷题 | 更多练习 |
相关链接
路径D-DSA算法刷题 | 二维几何基础 | 凸包 | 半平面交
多平台练习
| 洛谷 | 本题单 | 竞赛基础 |
| POJ (北大) | PKU JudgeOnline | 经典题目，适合巩固 |
| HDU (杭电) | HDU OJ | 暑期多校训练 |
| Codeforces | Codeforces | 国际竞赛，适合提升 |