LG3630 [APIO2010]信号覆盖
前言
南海都有网络了，怎么北京还要覆盖信号啊
好久以前做的计算几何题了，回来复盘一下。
解法
首先，题目中各有一个条件很重要：
保证任何三个房子都不在同一条直线 上，任何四个房子都不在同一个圆上。
翻译一下，没有四点共圆，没有三点共线。
我们做这道题依赖于这个条件。
首先对于 \(A,B,C\) 三个点作的外接圆，一定覆盖这三个点，对于任何一个圆都是如此。那我们的答案可以表示为：
其中，\(C^3_n\) 是圆的总数，而 \(sum\) 是所有圆圆内的点的数的总和。
问题就转化为，如何求 \(sum\) 呢？
正难则反。
我们可以算每个点在多少个圆内部，对于第 \(i\) 个点，这个值我们记为 \(f_i\)。那么 \(sum=\sum\limits_{i=1}^n f_i\)。这样，我们就要考虑确定圆的三个点和点 \(i\)，也就是四个点。因此我们考虑这四个点组成的四边形。
如果组成凸四边形。 则如下图：
由于没有四点共圆的情况，一定没有对角和为 \(180\) 的可能。那么以 \(A,D,C\) 作圆，一定能覆盖 \(C\)，以 \(D,C,B\) 作圆，一定覆盖 \(A\)。所以一个凸四边形对 \(sum\) 做 \(2\) 的贡献。
如果组成凹四边形。 则如下图：
显然，只有以 \(C,B,D\) 作圆才能覆盖 另一个点 \(A\)，因此一个凹四边形对 \(sum\) 的贡献是 \(1\)。
问题再次被我们转化，变为有多少个凸四边形，多少凹四边形。设他们的数量分别为 \(x,y\)。我们有：
我们到底是求 \(x\)，还是求 \(y\) 呢？
由于
我们只需要求出凸多边形数量 \(x\) 即可。
但是，真的是这样做吗？我们发现这样做其实很难。
凹四边形的数量会比凸四边形数量好求得多。呵呵
如果你仔细想想，就会发现，每个凹四边形都有一个凹角，所以我们要求出凹角数量。我们令凸角数量为 \(a\)，凹角数量为 \(b\)，由于每个四边形有四个角，我们有：
又到了熟悉的岔路口，但这一次，我们选择计算凸角数量 \(a\)。
这个求法非常简单，直接枚举每个点作为原点，其他的点做极角排序。
用双指针扫一下，得到以某一条边为定边的小于 \(180\) 度的角的个数。即 \(i\) 为定边，到 \(j\) 为止的角小于 \(180\) 度，\(j+1\) 与 \(i\) 所夹的角大于 \(180\) 度。那么这个区间里面的凸角所属四边形有 \(C_{j-i+1}^2\) 个。
注意要破环为链。
这样我们就求得了 \(a\)，我们就可以依次求出 \(b,y,x,sum,ans\)。
最后输出 \(ans\) 即可。
最后时间复杂度为 \(O(n^2\log n)\)。