5ab_86_2 三色

5ab_juruo · 2023-09-29 15:25:18 · 题解

k=1

观察到只有凸包上的点有可能。把凸包求出来，然后拎出上面的颜色，每次询问 check 即可。

证明：一个单色半平面的存在性等价于只包含一个这种颜色的点的半平面。考虑朝半平面的方向移动直线，逼近不包含任何点的状态，此时即为凸包的切线，最后一个点也必然在凸包上。

k=2

我们扩展 k=1 的方法，考虑切了一种颜色的点后下一种颜色的备选。

对于原凸包上的同色连续段 L，将 L 中的点删掉，并对 L 上一个点，L，L 下一个点构成的多边形内部的非同色点求凸壳（包括两端的点）。将凸壳上的点和 L 对应颜色构成的点对计入答案。

考虑如何求解 L 对应的点集。将所有点按照 A_1 极角排序，设凸包上所有的点按照逆时针依次为 A_1,A_2,\cdots,A_m。

将多边形剖分成若干个形如 A_1A_iA_{i+1} 的三角形。显然每个凸包内部的点只在一个三角形中。

注意到，若点 j 属于 A_1A_iA_{i+1} 这个三角形，则 j 只有可能对 A_1，A_i 或 A_{i+1} 所在的连续段产生贡献。结论易证。

所以每个点最多对三段有贡献，总点数就不超过 3n，总答案对数也不超过 3n，点集内直接暴力求解凸包即可。

复杂度 O((n+q)\log n)。

k=3

大致还是延续 k=2 的思路，但是要进行一定的分类讨论：

• 有两种颜色在外凸包上，一种颜色在内部（包括了三种颜色都在外凸包上的情况）；
• 一种颜色在外凸包上，一种颜色在内凸包上，还有一种要再往里面走一层（包括了两种颜色都在内凸包上的情况）。

主要的问题是，在 k=2 时，对于每个内部凸包上的点总存在一个半平面能截到外部凸包上的点，但这个结论在 k=3 的第一个 case 并不成立。所以还需要额外做个双指针状物，来检查能否覆盖到。

复杂度和 k=2 一致，带个不知道多少的常数。

代码