半平面交

首先是定义

一条直线和直线的一侧称为一个半平面。
半平面是一个点集，因此是一条直线和直线的一侧构成的点集。当包含直线时，称为闭半平面；当不包含直线时，称为开半平面。

一般来讲,都写成$ax+by+c\ge 0$.
是不是很眼熟,线性规划记得不,还有各种鬼畜应用题.用来求$(x,y)$的取值范围.
然后半平面交呢….就是把一堆半平面的交集求出来,就是半平面交了.
$\begin{cases}
a_1x+b_1y+c_1\ge 0\\
a_2x+b_2y+c_2\ge 0\\
…
\end{cases}$
昂,就这样子,画画图,就发现是个线性规划问题了…

哦,还有多边形的核
定义是:

如果一个点集中的点与多边形上任意一点的连线与多边形没有其他交点，那么这个点集被称为多边形的核。

然后求解也很简单,也是半平面交,以逆时针方向为正方向,将多边形每个边看成$ax+by+c\ge 0$,求一下交集,就是答案.

如何求解

两种方法,一种分治,一种排序增量法,叫$S\&I$算法好像.
当然,工具人只学简单的2333.

• 我们以逆时针为正方向,半平面为向量方向的左手.
• 维护一个双端队列
• 加入一个直线,就判断$tail-1$和$tail$的交点在该直线的哪边.
  1. 在右面,说明$tail$的直线被新加入的直线覆盖了,于是$tail-=1$
  2. 在左面,不做处理
• 对于队首元素,进行同样操作.
• 放入队列中
• 全部遍历结束后,再分别将$\{tail-1,tail,head\}$以及$\{head+1,head,tail\}$这两种情况的三个直线分别判断.

bool cmp(Line l1, Line l2) //半平面交的极角排序
{
    return bijiao(l1.poe, l2.poe) == 0 ? zhengfu(chaji(l1.b - l1.a, l2.b - l1.a)) > 0 : l1.poe < l2.poe;
}
bool check(Line a, Line b, Line c) //判断a,b交点是否在c的右边
{
    point o = zhixian_zhixian_jiaodian(a, b);
    return zhengfu(chaji(c.b - c.a, o - c.a)) < 0;
}
void banpingmian_jiao(int& head, int& tail, Line L[], int t) //求半平面交
{
    sort(L + 1, L + t + 1, cmp);
    head = 1, tail = 0;
    int cnt = 0;
    for (int i = 1; i < t; i++) {
        if (bijiao(L[i].poe, L[i + 1].poe) == 0)
            continue;
        L[++cnt] = L[i]; //因为排过序，即使极角相同，后面的也比前面的优
    }
    L[++cnt] = L[t];

    for (int i = 1; i <= cnt; i++) {
        while (head < tail && check(q[tail - 1], q[tail], L[i]))
            tail--;
        while (head < tail && check(q[head + 1], q[head], L[i]))
            head++;
        q[++tail] = L[i];
    }

    while (head < tail && check(q[tail - 1], q[tail], q[head]))
        tail--;
    while (head < tail && check(q[head + 1], q[head], q[tail]))
        head++;
}

例题推荐

• JLOI2013 赛车
• CQOI2006 凸多边形
• SCOI2015小凸想跑步
  1. 题解:My blog