本文从WordPress迁移而来, 查看全部WordPress迁移文章
二分 + 2-sat判定
题意:平面上有n个点,每个点有一个属于自己的区域,这个区域一定是一个正方形,另外这个区域一定出现在点的正上方或正下方,在正上方时,点在正方形下边的中点;在正下方时,点在正方形上边的中点。你可以把每个点对应的区域放在上方或下方,但是要令所有的点的区域不能相交(如果只是公用了边,不算相交)。在满足不想交的情况下,令区域最大(即正方形边长最大)
因为顶点坐标范围给出了,所以我们是可以知道正方形的大小范围的,用二分去枚举正方形的大小,看看在当前的大小下,能不能满足所有区域都不想交,能满足的话,说明是个可行解,那么就试着增大正方形的大小,看看还是否能满足,所以向上二分。如果当前不能满足的时候说明正方形太大了,那么就向下二分
至于怎么判断是否所有区域可以不想交,就是使用2-sat来判断的
一个点的区域可上可下,这很符合2-sat的模型,所以对于一个顶点,区域在上方和在下方用a,~a来表示
在判断之前我先对所有点进行了一次纵坐标的升序排序(横坐标不用排),这个排序并不是必须的,但是我排了序,更方便处理一些
下面看看怎么构图
枚举图中任意两点u,v,设当前二分枚举出来的正方形边长为s,因为排序了,所以约定yv >= yx
两点的区域能相交的一个条件就是他们的水平距离要小于s,即abs(xu-xv) < s,否则就是高度如何,都是不会相交的。所以两点满足abs(xu-xv) < s后,我们在进一步判断
yv = yu , 这个时候,u和v的区域必须一上一下,否则必然相交,所以可以找到必然关系
u->~v , ~u->v , v->~u , ~v->u
0 < yv - yu <= s , 这时候其实可以知道,只有当u的区域在下方,v的区域在上方时,他们才不会出现相交,否则其他任何摆放都会出现相交,所以这是个固定操作,固定u摆下方v摆上方
u->~u , ~v->v
s < yv - yu <= 2s , 当u放上方,v放下方的时候才会发生相交(其他情况不会),这是一对矛盾关系,可以推出必然关系,就是u在上方时v必在上方,v在下方时u必在下方
u->v , ~v->~u
2s < yv - yx,这样不会出现矛盾关系,结束了
每次二分答案后,就利用s来构一次图,然后进行判定即可
1 | /* |