BZOJ 1913: [Apio2010]signaling 信号覆盖

Brief description:

一个平面上 n 个点,随机选 3 个点构成一个圆,问期望有多少个点在这个圆内(包含圆上)。
数据保证没有 4 点共圆、3 点共线和重点。

Analysis:

http://wenku.baidu.com/link?url=Tlf5ltO7LTRqCd4NrmQKj_i34NiCUQ2pgW4q-t3vCK-IhFJA-mqZXXVw922QW4sTMnjQGZWY-YPTjxdH73syUpydJhVIxQ8iiBKEylZMj4m
http://hzwer.com/6743.html

因为保证没有四点共圆,我们只考虑包含的情况。暴力做法,O(n3) 枚举每一个圆 ,暴力检查有多少点在圆内,时间复杂度 O(n4)。
我们需要避免枚举所有圆,考察每一组四边形对答案的贡献。可以证明,每一组凹四边形对答案的贡献为 1,凸四边形对答案的贡献为 2。

证明?


对于任意四边形,我们首先找到其最小覆盖圆,考虑 ABC 三个点组成的三角形:

  • 如果第四个点 D 在三角形内部,那么对应凹四边形的情况,显然只有当选择 ABC 时才会产生贡献。
  • 如果第四个点 D 在三角形其他位置,例如在 I 区,那么有 ABC、ABD 都会产生贡献,I、III 区域类似。

如何统计凹四边形和凸四边形的数量?

算法 1:O(n3)
我们可以枚举任意两个点,然后求在这两个点左侧的点的个数来计算构成的四边形的个数。
可以看出,凸多边形会被计算 4 次,凹多边形会被计算 3 次,然后减去2倍的多边形总数,就是我们要求的结果。

算法 2:O(n2logn)
考虑一某个点为中心的凹四边形,我们枚举中心点,对其他点极角排序,two point 减去所有不合法的情况即可。

https://github.com/lychees/ACM-Training/tree/master/Archive/BZOJ/1913%20%5BApio2010%5Dsignaling%20%E4%BF%A1%E5%8F%B7%E8%A6%86%E7%9B%96%E3%80%90%E6%9E%81%E8%A7%92%E6%8E%92%E5%BA%8F%E3%80%91