旋转卡壳|学习笔记

· · 个人记录

【优秀blog】

题目大意：给你一个凸多边形，求出凸多边形内最大距离（凸多边形的直径）。

对于一个凸多边形随便选一条边，然后枚举出离这条边最远的点。

如图选定AB，最远点是E，过E作AB平行线。我们可以得到以E为其中一个点的最大距离（要么是AE要么是BE）。

接下来我们顺时针旋转两条平行线，使某一条线与凸多边形的边重合。上图中，过点E的平行线顺时针旋转后与EF重合，AB变为过B的关于EF平行的平行线。

我们得到以点B为其中一个点的最大距离（要么是BE要么是BF）

继续顺时针旋转两条平行线，就能得到凸多边形的直径。

【POJ-2187模板题】