虎！虎！虎！

Purslane · 2025-05-14 16:02:16 · 题解

Solution

爆标了兄弟们，稳定 16 次询问，不需要任何随机化（事实上只能证明是 24）。

先放一下 loj 的通过记录：AC Link。

首先考虑怎么做 60 分。前几个 Sub 的特征是，k=2n。

考虑将整张图三角剖分。对于一个平面图，有欧拉公式 V - E + F = 1。而 E \ge \frac{3}{2} F，得 F \le 2n。这样只需要 2n 次询问就可以确定虎在哪个多边形中。

不过有个问题：为什么一定能三角剖分，怎样三角剖分？

（注意本题没有三点共线，后面就不要考虑很多 corner case 了。）考虑将所有点按照 x 排序，维护后缀凸包。

显然后缀凸包之间互相包含，而且并不相同。每加入一个点，相当于凸包外一个点和这个凸包作切线。那么会新增一个凸壳和一个点的之间的连边。而整个图实质上就剖分成这些“月牙”型结构的并，如下图所示。

考虑二分出一个后缀使得老虎恰好在这个后缀的凸包中。那么老虎肯定在这个凸包新增的月牙中。

对着月牙做一次二分就可以。这样一次询问只用两次二分。

如何对月牙作二分呢？我们需要判定老虎是不是在月牙的前 k 个三角形中。直接查询包含他们的最小凸包（这个凸包一定是首尾端点构成的三角形。可能会包含之前凸包的部分，但是我们保证了老虎不在里面，所以是无所谓的）。