首先这个矩形的一条边肯定在凸包上。那么可以求出凸包然后枚举边，用类似旋转卡壳的方法求出另外三条边的位置，也就是求出以它为底最上面最右边最左边的点的位置。离它最远的点可以用叉积求，最左最右的可以用点积求。顺便注意精度问题，因为很小的时候可能会输出-0.00000，所以特判一下，当坐标小于eps的时候强制它等于0就行了首先这个矩形的一条边肯定在凸包上。那么可以求出凸包然后枚举边，用类似旋转卡壳的方法
阅读背景：
P3187 [HNOI2007]最小矩形覆盖
来源：互联网
分享到：
