「JOISC 2012」星座(凸包)

传送门

题意

平面上有 \(n\) 个点,保证任意三点不共线。有黑白两种颜色,一些点已经确定了一种颜色,其余点的颜色尚未确定。

对于一种染色方案,我们可以进行若干次操作,每次可以在两个同色点之间连一条直线段,但是要保证连的线段互不相交(除了在端点处可以相交)。如果最后每种颜色的点都能形成生成树,那么称这种染色方案是合法的。问有多少种合法的染色方案,对 \(10^9 + 7\) 取模。

数据范围:\(n \le 2 \times 10^5\)。

分析

考虑染色方案合法的充要条件。考察点集的凸包:

情况 1:凸包上点的颜色全部相同。不妨设其为黑色,我们任取内部一个白色点,以它为中心对凸包做三角剖分。先不连任何边,对于每个顶点一白两黑(或一黑两白)的三角形进行递归构造:若三角形内至少有一个白点,那么把它和三角形的白色顶点连边,并递归剖分出的三个三角形;若内部全是黑点,直接全连上某个顶点即可。通过这种构造就能让黑点、白点联通。因此这种情况合法。

情况 2:凸包由一个黑色连续段和一个白色连续段构成。此时也可以把凸包剖分成若干个一白两黑或一黑两白的三角形,继续使用上述递归算法。因此这种情况也合法。

情况 3:凸包上有超过一个黑色连续段。不妨考虑有两个黑色连续段的情况,设黑色连续段为 \(A, B\),白色连续段为 \(X, Y\)。那么 \(A, B\) 之间和 \(X, Y\) 之间都至少要连一条边,而这两条边一定会相交。因此这种情况不合法。

有了上述分析,接下来只要求出凸包,然后分类计数即可。

上一篇:JOISC 2015 简要题解


下一篇:thinkphp6: 生成带logo的二维码(php 8.1.1 / thinkphp v6.0.10LTS )