二维空间中包含原点的凸k边形计数算法咨询

核心结论 #

对于固定k，存在时间复杂度为O(n logn)的算法，统计凸位置n个点中包含原点的非退化凸k边形数量。

算法步骤 #

1. 极角排序
   将所有点按相对于原点的极角从小到大排序，得到环形序列 ( p_0, p_1, ..., p_{n-1} )。这一步的时间复杂度为O(n logn)，是整个算法的时间瓶颈。

2. 双指针确定半平面区间
   复制排序后的数组得到 ( p_0, ..., p_{2n-1} )（处理环形边界），用双指针遍历每个起点 ( i )（0≤i<n），找到最大的 ( j ) 使得 ( p_i ) 到 ( p_j ) 的极角差≤π（即所有 ( p_i ) 到 ( p_j ) 的点都在过原点的同一闭半平面内）。由于极角有序，双指针遍历的时间复杂度为O(n)。

3. 预处理组合数
   固定k，递推预处理组合数 ( C(t, k-1) )（t从0到n-1），利用公式 ( C(t, k-1) = C(t-1, k-1) + C(t-1, k-2) )，边界条件为 ( C(0, k-1)=0 )、( C(k-1, k-1)=1 )。预处理时间O(n)。

4. 计算全在半平面内的k边形数量
   对每个i，计算区间内选k-1个点的组合数 ( C(m_i - 1, k-1) )（( m_i = j - i + 1 ) 是当前半平面内的点总数），将所有值求和得到S。由于每个全在半平面内的k边形会被其k个顶点各统计一次，因此实际数量 ( T_k = S / k )。

5. 计算包含原点的k边形数量
   总凸k边形数为 ( C(n, k) )，包含原点的数量为：
   [
   \text{答案} = C(n, k) - T_k
   ]

关键说明 #

• 该方法基于凸多边形包含原点的充要条件：不存在过原点的直线，使得所有k个顶点都在直线的同一侧，通过总数量减去全在半平面内的数量得到结果。
• 由于题目限定非退化凸k边形，可假设所有点的极角互不相同，避免极角相等导致的边界歧义。

内容的提问来源于stack exchange，提问作者Neremintos