自动搬运

查看原文

来自洛谷，原作者为

	5ab_juruo May you find some comfort here

搬运于2025-08-24 22:50:44，当前版本为作者最后更新于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$ 一致，带个不知道多少的常数。

代码