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 减去所有不合法的情况即可。
