LG3630 [APIO2010]信号覆盖(计算几何)

LG3630 [APIO2010]信号覆盖

前言

南海都有网络了,怎么北京还要覆盖信号啊

好久以前做的计算几何题了,回来复盘一下。

解法

首先,题目中各有一个条件很重要:

保证任何三个房子都不在同一条直线 上,任何四个房子都不在同一个圆上。

翻译一下,没有四点共圆,没有三点共线。

我们做这道题依赖于这个条件。

首先对于 \(A,B,C\) 三个点作的外接圆,一定覆盖这三个点,对于任何一个圆都是如此。那我们的答案可以表示为:

\[ans=\frac{sum}{C_n^3}+3 \]

其中,\(C^3_n\) 是圆的总数,而 \(sum\) 是所有圆圆内的点的数的总和。

问题就转化为,如何求 \(sum\) 呢?

正难则反。

我们可以算每个点在多少个圆内部,对于第 \(i\) 个点,这个值我们记为 \(f_i\)。那么 \(sum=\sum\limits_{i=1}^n f_i\)。这样,我们就要考虑确定圆的三个点和点 \(i\),也就是四个点。因此我们考虑这四个点组成的四边形。

如果组成凸四边形。 则如下图:

LG3630 [APIO2010]信号覆盖(计算几何)

由于没有四点共圆的情况,一定没有对角和为 \(180\) 的可能。那么以 \(A,D,C\) 作圆,一定能覆盖 \(C\),以 \(D,C,B\) 作圆,一定覆盖 \(A\)。所以一个凸四边形对 \(sum\)\(2\) 的贡献。

如果组成凹四边形。 则如下图:

LG3630 [APIO2010]信号覆盖(计算几何)

显然,只有以 \(C,B,D\) 作圆才能覆盖 另一个点 \(A\),因此一个凹四边形对 \(sum\) 的贡献是 \(1\)

问题再次被我们转化,变为有多少个凸四边形,多少凹四边形。设他们的数量分别为 \(x,y\)。我们有:

\[x+y=C_n^4 \]

我们到底是求 \(x\),还是求 \(y\) 呢?

由于

\[sum=2x+y=C_n^4+x \]

我们只需要求出凸多边形数量 \(x\) 即可。

但是,真的是这样做吗?我们发现这样做其实很难。

凹四边形的数量会比凸四边形数量好求得多。呵呵

如果你仔细想想,就会发现,每个凹四边形都有一个凹角,所以我们要求出凹角数量。我们令凸角数量为 \(a\),凹角数量为 \(b\),由于每个四边形有四个角,我们有:

\[a+b=4\cdot C_n^4 \]

又到了熟悉的岔路口,但这一次,我们选择计算凸角数量 \(a\)

这个求法非常简单,直接枚举每个点作为原点,其他的点做极角排序。

LG3630 [APIO2010]信号覆盖(计算几何)

用双指针扫一下,得到以某一条边为定边的小于 \(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)\)

LG3630 [APIO2010]信号覆盖(计算几何)

上一篇:jQuery 学习之javascript回顾001---Getting started javascript


下一篇:CSS3 @font-face