答案显然是一个凸包。注意到求凸包最远点对的过程就是一个旋转卡壳。我们可以定义 $dp(v,i,j)$ 为当前转到的方向是 $v$，$i$ 和 $j$ 分别是最小点和最大点的最大面积。转移实际上是将所有点对的连线排序，转到平行于 $i,j$ 连线的方向时可以将 $(i,k)$ 转移到 $(j,k)$，因此时间复杂度 $O(n^3)$。
QOJ.ac
QOJ
As we are currently experiencing an overwhelming number of web requests for fetching user submissions, we have temporarily disabled the full submissions list. You must now be logged in to view submissions.
Discussion #164 for Problem #7220. The Defense Fence
Type: Editorial
Status: Open
Posted by: jiangly
Posted at: 2025-12-12 23:45:24
Last updated: 2025-12-12 23:45:28
题解
Comments
No comments yet.