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

我真是没辙了要画图还不知道会不会挂。。温馨提示本文不是题解只是根据董晓老师的半平面交教程做的笔记配合视频会更好理解。视频链接强烈推荐膜拜老师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; }正常的半平面交的板子是有踢队头的不过本题很特殊。一开始的那条边肯定能看到因为斜率最小的直线在时总是最高的。因此它总是可见的永远不会被完全覆盖于是双端队列退化成单调栈了其实整个代码最需要理解的地方就是两条线段直线的交点和踢队尾的时候叉积是怎么发挥作用的。首先来看交点以下图片建议配合代码 cross 函数食用图中深蓝和红色的是要计算交点的向量浅蓝是向量到交点的延长线粉色同理。我们都知道叉积的绝对值就是俩向量构成的平行四边形面积的值所以也就有淡紫色的平行四边形是浅黄色的平行四边形是代码中设也就是俩平行四边形面积比又因为俩四边形底相同所以面积比就是与底相对应的高的比。蓝色加粗的是的高红色加粗的是的高我们又发现因为平行四边形两底相等所以可以把那条红色的高平移到粉色下面刚好接着向量的终点平移过来后我们发现新构成的俩三角形和是相似的而它们的高比就等于斜边比也就是向量的长度与向量延长到交点的长度之比。所以代码最后就轻松求出了交点。这时就有同学要问了求交点直接代入俩直线方程不好吗哎还真没错但你想想如果要处理直线交点还有特殊情况平行线无交点重合线无限多交点写判断起来可麻烦更别说你还得解方程。而且俩直线斜率很接近几乎平行时那下面的分母就会很小精度问题也要考虑。而向量就没这烦恼不用分情况讨论几乎平行的时候也不是大除以小是小除以小。再来看看怎么踢队尾的橙色的是由的起点指向俩队尾交点的向量这时候根据右手法则叉积大于也就是三直线能好好相处构成多边形。right 函数返回不用踢队尾。另外一种情况这时候不满足右手法则叉积小于构成多边形显然不需要队尾于是踢队尾。当然还有叉积等于的情况也就是向量和向量在同一条直线上这样构成多边形和队尾也没啥关系照样踢。题单【题单】半平面交-CSDN博客