计算几何：半平面交

相当于中学的时候学的线性规划，用n条直线去切割一个平面，每条直线代表一定的限制，最后如果有解就会在中间留下一个凸核：

线性规划

多边形的核

什么是半平面交？

典型的例子：给你一个多边形，判断多边形内是否存在一个点，从这个点可以看到多边形周围所有的点。

1. 做法：

多边形的每条边都是一个约束条件，边的顺序为顺时针

用每条边的直线去切割当前平面：枚举平面点集中的点，假如当前点(p)在核外，

判断p-1与p+1是不是在核内，如果是，则肯定有交点

分别把求出的交点加入点集

不断重复的做下去

最后点集中的点就是要求的的可行解

2. 主代码

void halfPlaneIntersection()
{
    int i,j;
    sort(order,order+ln,cmp);
    for (i=1,j=0;i<ln;i++)
        if (dblcmp(l[order[i]].angle-l[order[j]].angle)>0)
            order[++j]=order[i];
    ln=j+1;
    dq[0]=order[0];
    dq[1]=order[1];
    bot=0;
    top=1;
    for (i=2;i<ln;i++)
    {
        while (bot<top&&judge(l[order[i]],l[dq[top-1]],l[dq[top]]))
            top--;
        while (bot<top&&judge(l[order[i]],l[dq[bot+1]],l[dq[bot]]))
            bot++;
        dq[++top]=order[i];
    }
    while (bot<top&&judge(l[order[bot]],l[dq[top-1]],l[dq[top]]))
        top--;
    while (bot<top&&judge(l[order[top]],l[dq[bot+1]],l[dq[bot]]))
        bot++;
    dq[++top] = dq[bot];
}

3. 更多的一些要求

核的面积——三角形分割

核的重心——重心公式

现在可以过水题了……

poj 3335

传送门：http://poj.org/problem?id=3335

poj 2451

传送门：http://poj.org/problem?id=2451

然而我们需要更快一点的算法

先引用一下nlgn算法的介绍，在zzy论文里也有详细介绍.

传送门：http://wenku.baidu.com/link?url=-SuOjErNbhSY3NBrL7WtJHAL1F6SzzuAjlm1TV0y8QlTlK7vzlxQ7NHvH7K5WSnOqaipIEGTjZ7czJYobcej0YyopbsQD9Fyy1p3rD96K8u

step1.

将所有半平面按极角排序，对于极角相同的，选择性的保留一个。 O(nlogn)

step2.

使用一个双端队列(deque)，加入最开始2个半平面。

step3.

每次考虑一个新的半平面：
 a.while deque顶端的两个半平面的交点在当前半平面外:删除deque顶端的半平面
 b.while deque底部的两个半平面的交点在当前半平面外:删除deque底部的半平面
 c.将新半平面加入deque顶端

step4.

删除两端多余的半平面。

具体方法是：

 a.while deque顶端的两个半平面的交点在底部半平面外:删除deque顶端的半平面
 b.while deque底部的两个半平面的交点在顶端半平面外:删除deque底部的半平面
重复a,b直到不能删除为止。

step5:

计算出deque顶端和底部的交点即可。

然后就有更多奇怪的题了

一. bzoj 1038

传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1038

题意：给出一个村庄的轮廓，在这个村庄里可以在任意的地方建一个瞭望塔，这个塔需要足够高，使得能够看得村庄的全貌。求这个瞭望塔的最小高度。

思路：对于村庄中的每一条边，瞭望塔为了看见它，必须要在这个直线左侧的半平面区域。这样的话为了满足所有的边的需求，做一次半平面交，瞭望塔的最高点必须在所有边的半平面交的区域内。

二. poj 3525

传送门：http://poj.org/problem?id=3525

题意：给定一个凸多边形，求多边形中距离边界最远的点到边界的距离。

思路 : 每次将凸多边形每条边往里平移d，判断是否存在核；二分d即可。

最后是你们要的模（fu）板（li）||ヽ(￣▽￣)ノミ|Ю

#include <stdio.h>
#include <string.h>
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <math.h>
using namespace std;
const int N = 300005;
const double EXP = 1e-8;
typedef long long LL;
struct point
{
    double x , y ;
}p[N];
struct line
{
    point a,b;
    double angle;
}l[N];
int cas,n,top,bot,order[N],ln,dq[N];
double abs(double a)
{
    if (a<0)
        return -a;
    return a;
}
int dblcmp(double k)
{
    if (abs(k)<EXP)
        return 0;
    return k>0?1:-1;
}
double det(point p0,point p1,point p2)
{
    return (p1.x-p0.x)*(p2.y-p0.y)-(p1.y-p0.y)*(p2.x-p0.x);
}
bool cmp(int a,int b)
{
    int d = dblcmp(l[a].angle-l[b].angle);
    if (d==0)
        return dblcmp(det(l[a].a,l[b].a,l[b].b))<0;  //  逆时针输入（取左侧）时为">"
    return d<0;
}
void getIntersect (line l1,line l2,point &p)
{
    double d1,d2;
    d1=det(l2.a,l1.b,l1.a);
    d2=det(l1.b,l2.b,l1.a);
    p.x=(l2.a.x*d2+l2.b.x*d1)/(d2+d1);
    p.y=(l2.a.y*d2+l2.b.y*d1)/(d2+d1);
}
bool judge (line l0,line l1,line l2)
{
    point p;
    getIntersect(l1,l2,p);
    return dblcmp(det(p,l0.a,l0.b))>0;		//  逆时针输入（即取左侧）时为"<"
}
void addline(double x1,double y1,double x2,double y2)
{
    l[ln].a.x=x1;
    l[ln].a.y=y1;
    l[ln].b.x=x2;
    l[ln].b.y=y2;
    l[ln].angle=atan2(y2-y1,x2-x1);
    order[ln]=ln;
    ln++;
}
void halfPlaneIntersection()
{
    int i,j;
    sort(order,order+ln,cmp);
    for (i=1,j=0;i<ln;i++)
        if (dblcmp(l[order[i]].angle-l[order[j]].angle)>0)
            order[++j]=order[i];
    ln=j+1;
    dq[0]=order[0];
    dq[1]=order[1];
    bot=0;
    top=1;
    for (i=2;i<ln;i++)
    {
        while (bot<top&&judge(l[order[i]],l[dq[top-1]],l[dq[top]]))
            top--;
        while (bot<top&&judge(l[order[i]],l[dq[bot+1]],l[dq[bot]]))
            bot++;
        dq[++top]=order[i];
    }
    while (bot<top&&judge(l[order[bot]],l[dq[top-1]],l[dq[top]]))
        top--;
    while (bot<top&&judge(l[order[top]],l[dq[bot+1]],l[dq[bot]]))
        bot++;
}
bool isCore()
{
    if (top-bot>1)
        return true;
    return false;
}
int main ()
{
    int i;
    scanf ("%d",&cas);
    while (cas--)
    {
        scanf ("%d",&n);
        for (i=0;i<n;i++)
            scanf("%lf%lf",&p[i].x,&p[i].y);
        for (ln=i=0;i<n-1;i++)
            addline(p[i].x,p[i].y,p[i+1].x,p[i+1].y);
        addline(p[i].x,p[i].y,p[0].x,p[0].y);
        halfPlaneIntersection();
        if (isCore())
            printf("YES\n");
        else
            printf("NO\n");
    }
return 0 ;
}

作者：潘喆沈思远
2016 年 7月 11日

什么是 半平面交 ？