amath

三维凸包

Felicia

Mar 28, 2008

1 三维凸包的复杂度

定理 1
设`P`为包含`n`个顶点的任意凸多面体。则`P`中所含的边不会超过`3n – 6`条，所含的面不会超过`2n – 4`张。
证明：该凸多面体`P`可看做平面图。在与`P`对应的图中，每张面都是至少由`3`条边围成的，而且每条边都与两张面相关。因此我们得到`2n_(e) <= 3n_(f)`。代入欧拉公式`n - n_(e) + n_(f) = 2`，得到：`n + n_(f) -2 <= 3n_(f) / 2`。于是有`n_(f) <= 2n - 4`，再代入欧拉公式得到`n_(e) <= 3n - 6`。

因此我们有如下结论：
推论 1
`n`个点的三维凸包的边数为`O(n)`，面数为`O(n)`。

2 三维凸包的算法

计算三维凸包的算法有很多种，包括：随机增量法，卷包裹法，Graham扫描法等。其中随机增量法实现起来很简单，尤其适合信息学竞赛的应用。下面给出随机增量算法：

1. 在`P`中找出4个不共面的点`p_1,p_2,p_3,p_4`，构成一个四面体，作为初始凸包。
2. 将其余各点随机排列，按照以下规则加入凸包（假设加入的点是`p`）：
   1. 将凸包看作实体，确定从`p`能够看到的面。
   2. `p`的可见面与不可见面的交界称为地平线，将`p`与地平线上的每个点连接，生成若干个新的面。
   3. 删去原先从`p`可见的面。

3 随机增量算法的演示程序

endamath

原文出自珞珈山水BBS
这次比赛我出了3道题目: A题Exchange, D题Matrix, E题Necklace.
(全文 …)

校赛预选赛结束了。我的心情不是很好。从寒假开始一直到现在，GCC都在不遗余力地为这次校赛准备题目。在出题的过程中，我感觉，要出好题的确太难了。
(全文 …)

本文转载自菜鱼的blog

原文题为《常系数线性递推的第n项及前n项和》

（一）Fibonacci数列`F_n = F_{n-1} + F_{n-2}, F_1 = F_2 = 1`的第`n`项的快速求法（不考虑高精度）.

解法：

考虑`1 xx 2`的矩阵`[F_{n-2}, F_{n-1}]`。

根据Fibonacci数列的递推关系，我们希望通过乘以一个`2 xx 2`的矩阵，得到矩阵`[F_{n-1},F_n]=[F_{n-1},F_{n-1}+F_{n-2}]`

很容易构造出这个`2 xx 2`矩阵`A`，即：
`[(0, 1), (1, 1)]`
所以，有`[F_1, F_2]A ＝ [F_2, F_3]`

又因为矩阵乘法满足结合律，故有：

`[F_1,F_2]A^{n-1} ＝ [F_n,F_{n+1}]`

这个矩阵的第一个元素即为所求。

至于如何快速求出`A^{n-1}`，相信大家都会，即递归地：`n`为偶数时，`A^n = (A^(n/2))^2`；`n`为奇数时，`A^n=(A^(n/2))^2*A`。

问题（一）解决。
(全文 …)