引言 计算几何对于很多刚接触OI的同学们是不会涉及的,当逐步进入省选范畴之后,计算几何的应用就非常广了。 本文同 洛谷日报 #142。 你需要知道? 在学习计算几何(至少是这篇文章)之前,你需要了解以下这...
旋转卡壳
洛谷 P3187 [HNOI2007]最小矩形覆盖 题解【凸包】【旋转卡壳】
感觉对旋转卡壳的理解又多了一点点……不过这个题莫名卡精度啊 题目描述 给定一些点的坐标,要求求能够覆盖所有点的最小面积的矩形,输出所求矩形的面积和四个顶点坐标 输入输出格式 输入格式: 第一行...
凸包 旋转卡壳 学习笔记【计算几何】
以前的凸包可能是死记硬背的……不过现在算理解了。 凸包 定义 凸包就是求一个周长最小的,并且能包围所有给定点的多边形。当多边形表面存在凹陷时,根据三角不等式\(\left\{\begin{matrix}a+b>c\\ b...