CheckerFreeness

作者:汪乐平 钟知闲

关键词:凸四边形判定 压位

题目简述

给出W个白点和B个黑点,保证没有重点,且任意三点不共线。问是否存在一个凸四边形,满足一对相对的顶点均为白点,另一对相对的顶点均为黑点。1W,B222,1x,y10000000

算法一

枚举每一对白点和黑点,显然四边形是凸的当且仅当对角线是相交的,所以用叉积判断两个白点连成的线段和两个黑点连成的线段是否相交即可,时间复杂度O(W2B2)

算法二

换一种方法判断是否是凸四边形。假设已知一个黑点和两个白点,显然另一个黑点在下图所示的深色区域时这个四边形才是凸的。

考虑这个深色区域中的点有什么性质。设数组b[i][j][k]表示ikj是否小于π(这里认为ikj+jki=2π)。假设已知的两个白点是w1w2,黑点是b1,那么深色区域中的点x就满足b[w1][b1][x]b[w2][b1][x]=1b[w1][w2][x]b[w1][w2][b1]=1。所以预处理出b,枚举w1,w2,b1,x就可以判断有没有符合条件的凸四边形了。

如果暴力枚举时间复杂度仍然是O(W2B2)的,但这种判断方法可以用bitset压位加速,所以判断的时间可以降为O(W2B2/w),其中w表示字长。数组b三维的大小分别为WW+BB,求b[i][j][k]的值可以用叉积O(1)计算,所以预处理b的时间复杂度为O((W+B)WB)。所以总的时间复杂度为O((W+B+WB/w)WB)

算法三

在上述算法基础上加一些小优化。考虑先枚举一个白点 A,然后将剩下的点以 A 为中心极角排序,再枚举第二个白点 B。因为 A,B 与另外两个黑点 C,D 构成凸四边形 ACBD 的条件是 C,D 在直线 AB 两侧,且 CAB+DAB<πCBA+DBA<π,所以将黑点按照在直线 AB 的哪一侧分成两组,按 CAB 从大到小的顺序枚举一侧的黑点 C,维护另一侧满足 CAB+DAB<π 的黑点 DDBA 的最小值 DBAmin,如果 CBA+DBAmin<π,那么就说明找到了这样的凸四边形,返回 NO,如果始终没找到,返回 YES。由于已按极角排序,满足 CAB+DAB<π 的黑点 D 在序列中是连续区间(环状的,可能是一段后缀加一段前缀),每枚举一个 C 就扩展一下这个区间,即可对于每对 A,B 做到 O(n) 的复杂度,总复杂度为 O(n3)n 为点数)。

results matching ""

    No results matching ""