P4196 [CQOI2006]凸多边形 /【模板】半平面交 题解

Lagerent · 2023-05-15 18:07:41 · 题解

半平面交

0.前言

关于我写代码的一些习惯与声明：

typedef pair<double, double> PDD;

#define x first
#define y second

struct Line {
    PDD st, ed;
}line[N];

PDD operator - (PDD a,  PDD b) {
    return {a.x - b.x, a.y - b.y};
}

1.前置知识

1.1 高中平面向量相关知识

1.2 向量叉积 (cross)

1.2.1 几何意义：由两个向量围成平行四边形的有向面积。

1.2.2 规定：第二个向量在第一个向量的逆时针方向为正，顺时针方向为负。

double cross(PDD a, PDD b) {
    return a.x * b.y - a.y * b.x;
}

double area(PDD a, PDD b, PDD c) {
    return cross(b - a, c - a);
}

1.3 求直线交点 (get line intersection)

设交点为 p + t \times \vec{v}。

令 \vec{u} = p - q，

根据三角形相似，不难得出 t = \frac{\vec{w} \times \vec{u}}{\vec{v} \times \vec{w}}。

PDD gli(PDD p, PDD v, PDD q, PDD w) {
    auto u = p - q;
    double t = cross(w, u) / cross(v, w);
    return {p.x + v.x * t, p.y + v.y * t};
}

PDD gli(Line a, Line b) {
    return gli(a.st, a.ed - a.st, b.st, b.ed - b.st);
}

1.4 判断两直线交点是否在另一直线右侧

设两直线交点为 o。

判断这条直线上的任一条线段和这个交点围成的三角形面积符号即可。

bool on_right(Line a, Line b, Line c) {
    auto o = gli(b, c);
    return sign(area(a.st, a.ed, o)) <= 0;
}

1.5 求某条直线与水平方向的夹角

设这条直线上的某个点为 (x, y)，与水平方向的夹角为 \alpha。