当前位置：首页 > news >正文

【超多图！笔记】[HNOI2008] 洛谷P3194 水平可见直线 [半平面交]

news 2026/7/13 22:06:43

~~我真是没辙了要画图，还不知道会不会挂。。~~

温馨提示：本文不是题解，只是根据董晓老师的半平面交教程做的笔记，配合视频会更好理解。

视频链接（强烈推荐！！膜拜老师TNT）

前置知识：

向量定义（自行百度或问 AI 就行）

知道叉积是什么，是怎么算的，了解右手法则

（向量向量就是叉积，右手立起来对准向量，四根手指指向的终点，再把四根手指往里收，恰好指向的终点，满足这个规则的俩向量叉积就大于）

注意：叉积不满足交换律！！

极角定义及其计算方法：

极角是一个向量与x轴正方向之间的夹角。

以下点 (x,y) 为从 (0,0) 出发指向 (x,y) 的向量。

举例：

点 (1, 0) 的极角是 0°
点 (0, 1) 的极角是 90°
点 (-1, 0) 的极角是 180°
点 (0, -1) 的极角是 270° 或 -90°

计算方法：

其实就是求的反函数值（自行百度），一般的取值范围是。

（弧度制为度）

但我们编程中有个，直接就可以得出该向量的极角，取值范围是。

（也就是包揽了整个度）

题面：

洛谷P3194

从正无穷往下看，只能看见多边形的边，就是半平面交。

解析：

先上注释版代码：

#include <bits/stdc++.h> using namespace std; const int N = 5e4 + 10; const double eps = 1e-12; // 极小值，用于浮点数比较，根据题目定 1e-多少 int n, ans[N]; struct point { double x, y; //点 }; struct line { point s, e; //向量，包含起点终点和编号 int id; //原始编号会因排序混乱，应题目要求输出答案时需要 } a[N], q[N]; //以下 operator都是重载运算符 point operator+(point a, point b) { //向量相加 return {a.x + b.x, a.y + b.y}; } point operator-(point a, point b) { //向量相减 return {a.x - b.x, a.y - b.y}; } point operator*(point a, double t) { //向量数乘 return {a.x * t, a.y * t}; } double operator*(point a, point b) { //叉积 return a.x * b.y - a.y * b.x; } double angle(line a) { // atan2(y,x)计算向量 (x,y)的极角（范围 -π到 π） return atan2(a.e.y - a.s.y, a.e.x - a.s.x); } bool cmp(line a, line b) { //按极角给向量排序 //（极角从小到大排序了就好框多边形） double A = angle(a), B = angle(b); if (fabs(A - B) > eps) { //角度有很明显差别时 return A < B; } else { //角度差距不明显（平行）时 //注意这下面的 *都是重载过的叉积运算 return (a.e - a.s) * (b.e - a.s) < 0; //用叉积判断 b在不在 a的左边 //注意一个是向量 a，一个是 a的起点到 b的终点！！ //就是右手法则，如果 a在 b的右边上面这一坨就大于 0，反之小于 0 //如果 a在 b的左边，则 a比 b优，那原先顺序不变，对应下面的： // if (angle(a[i]) - angle(a[i - 1]) < eps) continue; //搞过前面的 i-1 (a) 就不用搞 i (b) 了 } } point cross(line a, line b) { //求俩向量交点 point u = a.s - b.s; // b起点到 a起点 point v = a.e - a.s; // a起点到 a终点 point w = b.e - b.s; // b起点到 b终点 double t = (u * w) / (w * v); return a.s + v * t; //看不懂这段就先别看，看我代码下面的解释和图片 } bool right(line a, line b, line c) { point p = cross(b, c); // p是交点 return (a.e - a.s) * (p - a.s) <= 0; //这里我下面也有画图 //就是 a起点到 a终点的向量和 a起点到 bc交点的向量 判断位置，同上右手法则 //=0 代表俩向量重合，上面不判 =是因为题目说过直线不会相互重合 } void half_plane() { sort(a + 1, a + n + 1, cmp); //按极角排序 int head = 1, tail = 1; q[1] = a[1]; for (int i = 2; i <= n; i++) { if (angle(a[i]) - angle(a[i - 1]) < eps) { continue; //跳过角度相同的直线，保留最左侧 } //检查队尾直线是否无效 //当队尾 q[t]与队尾第二条直线 q[t-1]的交点 //在新直线 a[i]的右侧时，队尾直线无效 while (head < tail && right(a[i], q[tail], q[tail - 1])) { tail--; } q[++tail] = a[i]; } int len = 0; for (int i = head; i <= tail; i++) { //还在队里面的就是能框成多边形的，也就是能看见的 len++; ans[len] = q[i].id; } sort(ans + 1, ans + len + 1); for (int i = 1; i <= len; i++) { cout << ans[i] << " " ; } cout << endl; } int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n; for (int i = 1; i <= n; i++) { double A, B; cin >> A >> B; a[i] = {{0, B}, {1, A + B}, i}; //取 x为 0和 1的点 } half_plane(); return 0; }

（正常的半平面交的板子是有踢队头的，不过本题很特殊。

一开始的那条边肯定能看到，因为斜率最小的直线在时总是最高的。

因此它总是可见的，永远不会被完全覆盖，于是双端队列退化成单调栈了）

其实整个代码最需要理解的地方就是两条线段（直线）的交点，

和踢队尾的时候叉积是怎么发挥作用的。