官方题解只能做到 $O\left(n^4\right)$？玩的太差了。这题的理论最优复杂度是 $\Theta(n)$ 时间、$O(n)$ 空间。

设起点为 $s=(0,0)$，湖泊为简单多边形 $P$。令 $d(x)$ 表示从 $s$ 到 $x$、不经过湖泊内部的最短路径长度。要求的庄园就是可达区域 $R={x\notin\operatorname{int}P:d(x)\le k}$，而不是半径为 $2k$ 的区域。题目允许起点位于湖岸上，这一点必须处理。([QOJ][1])

最短路径除在多边形顶点处转折外，其余部分都是直线。否则可以将一个没有接触障碍物的折点拉直，使路径变短。因此，若一条最短路径最后经过的顶点为 $v$，则其长度为 $d(v)+|vx|$；直接从起点走到 $x$ 时，可以将 $s$ 本身视为这个“最后顶点”。这也是多边形障碍最短路径图按最后一个顶点划分区域的依据。

记 $V$ 为湖泊顶点与起点的集合，$\operatorname{Vis}(v)$ 为从 $v$ 直接可见的区域。对满足 $d(v)< k$ 的点，建立圆盘 $D_v$，其圆心为 $v$，半径为 $r_v=k-d(v)$。于是有

$$ R=\bigcup_{\substack{v\in V\\d(v)< k}}\bigl(D_v\cap\operatorname{Vis}(v)\bigr). $$

这里的可见性限制不能省略。事实上，许多小圆盘在欧氏意义下包含于起点的大圆盘中，但起点的大圆盘有一部分被湖泊挡住，小圆盘恰好负责补上绕过拐角之后才能到达的区域。

如果只要求得到一个多项式算法，可以建立可视图，跑最短路，然后处理上述区域并。但这不是理论上最快的方向：可视图本身就可能有 $\Theta(n^2)$ 条边。

更快的对象是最短路径图，记作 $\operatorname{SPM}(s)$。它把自由空间划分为总复杂度 $O(n)$ 的区域，每个区域有一个固定的最后顶点 $v$，并且在该区域内恒有 $d(x)=d(v)+|vx|$。区域边界由湖岸、直线窗口以及形如 $d(u)+|ux|=d(v)+|vx|$ 的双曲线弧组成。已有算法在自由空间完成三角剖分之后，能够用 $O(n+h\log h)$ 时间、$O(n)$ 空间构造它，其中 $h$ 是障碍物数量；包括三角剖分在内也有 $O(n+h\log^{1+\varepsilon}h)$ 的界。本题只有一个湖泊，因此得到 $O(n)$。

构造出最短路径图后，面积部分也不需要重新引入排序或两两求交。

考虑最后顶点为 $v$ 的一个区域，只需保留其中满足 $|vx|\le r_v$ 的部分。这个区域关于 $v$ 是星形的：若 $x$ 的最短路径最后经过 $v$，那么线段 $vx$ 上的点也可以沿同一个最短路径前缀到达；倘若其中某点能严格更快到达，接上剩余直线段就会使 $x$ 的路径更短。

沿区域已有的边界顺序处理即可。圆与一条湖岸或窗口只有常数个交点；当圆与两个区域之间的双曲线边界相交时，交点同时满足 $|vx|=k-d(v)$ 和 $|ux|=k-d(u)$，所以直接转化成两个圆的交点，同样只有常数个。全部区域的边界总复杂度是 $O(n)$，因此整个截取过程也是 $O(n)$。

尤其重要的是，不需要计算双曲线弧围成的面积。两个相邻区域中，可达部分沿公共边界的贡献方向相反，求和后自动抵消。最终只需保留可达区域真正边界上的圆弧，以及可达的湖岸片段。

记 $[A,B]$ 为二维叉积。根据边界积分，有向线段 $A\to B$ 的面积贡献为 $[A,B]/2$。对于圆心为 $C$、半径为 $r$、从角度 $\alpha$ 逆时针走到 $\beta$ 的圆弧，设起终点分别为 $A,B$，贡献为

$$ \frac12\left(r^2(\beta-\alpha)+[C,B-A]\right). $$

所有边都按照“可达区域在左侧”的方向处理。因此圆弧取逆时针方向，湖岸直接使用输入给出的顺时针方向；内边界的负面积会自然扣除，无须额外判断内外环。

这样，最短路径图构造和面积统计都为 $O(n)$，结合读取输入的 $\Omega(n)$ 下界，得到理论最优的 $\Theta(n)$。

提交记录：https://qoj.ac/submission/2942487 计算几何就是简单。