半平面交 专题训练

发布于 2018-03-11  4.71k 次阅读


半平面交就是求几个“向量”围成的半平面的过程,主要可以解决线性规划类型的问题。

个人感觉实现起来有几个要注意的地方,下面放上一个模板,在代码里附上了一些说明:

关于不等式的方向判断,ax+by+c>=0表示直线的左侧区域,方向的定义是在直线上取两个点,且两点满足“逆时针”的关系,那么这两个点组成的向量指向的方向是正方向(前方)。

关于精度,个人认为多数情况下可以直接比较,一般没有什么问题。但是不乏一些奇葩(BZOJ 1137),在judge()中必须加上eps才能通过。

※※注意:加边时一定要令-inf<=x<=inf,-inf<=y<=inf,否则上述算法是错误的※※

反例见下,可以自行手动模拟算法的过程(然而我做到最后一题才发现= =):半平面交一定要加框框

 

BZOJ1038: [ZJOI2008]瞭望塔

给出n个点组成的一座山峰,找出一个位置满足相对高度最低且能看到所有位置。

首先半平面交求出可行区域,之后问题转化为在两个区域内找出最近的距离。YY一下,发现最近的距离只有可能发生在拐点处,那么只要求出暴力每个拐点,然后暴力求出拐点处两个区域的界限高度就好了。

 

BZOJ2732: [HNOI2012]射箭

题意略。列出线性规划的式子直接上,裸题。

 

BZOJ3800: Saber VS Lancer

题意略。设总长度为单位1,第一项路程为a,第二项为b,那么第三项为1-a-b,在a+b<=1,a>=0,b>=0的框框里面搞事情即可。

 

BZOJ3199: [Sdoi2013]escape

感觉比之前的题综合了一点。对于每个点,列出n-1个式子,表示当前点为最近点的(x,y)的范围,再加上表示矩形区域界线的框框,如果当前区域边界包含框框,那么打个标记,然后把相邻的点连边,在合法的区域内跑个spfa/bfs求最短路。注意特判n=0以及点不在矩形区域内的情况。

 

BZOJ4445: [Scoi2015]小凸想跑步

给出凸多边形,求多边形内部一点与前两个点围出的三角形比其他任意三角形都小的概率。

线性规划直接上,注意加上多边形的边界,这是唯一一道1A的题= =(其他都被卡精度/想错了)

 

BZOJ1137 [POI2009]Wsp 岛屿

题意略。

转换设问,最短路就是最靠近(1,n)的边围成的显然我们不能搞出来O(n^2)条边来搞线性规划。

考虑优化图中的边数。假设最优的路径经过(a,b)、(c,d)的交点,那么一定不存在(a,t)(t>b)与(c,d)相交。因为原图为一个凸多边形,所以越“靠下”的边一定越短。

这样,我们只要给每个点连出一条边,再跑线性规划就可以搞定了。

卡精度,比较恶心。

 


Narcissus | HZOIer | zhuohaoyu1228@gmail.com | QQ 943382974