不知不觉简单的计算几何就快讲完了,这次我再讲讲旋转卡壳算法(看得我脑袋是有些卡壳QwQ)。这个算法和凸包有着很大的关系,所以建议没看凸包的同学去计算几何分类看一下凸包的求解方法。 先抛出一个问题 在二维平面上给定n个点,求距离最远的两个点之间的距离是多少? 看到这道题,大部分同学第一反应肯定是暴力——暴力枚举所有点对,然后求出最远的那一对相距的距离。这种方法当然没错,可是复杂度已经达到...
咳咳,上次写完凸包后,Blog就由于服务器的原因炸了两天:sob:这两天我试着研究了一下半平面交,发现其实和高中数学的“线性规划”有着很大的关系(什么你不会,问题不大),这篇博客就让你彻底学会求半平面交的面积。 写在前面 在这篇BLOG中,为了方便讲解我们默认把一条有向直线的左侧设为该半平面的有效区域。:smirk: 什么是半平面 大家都知道形如ax+by+c=0的图形称为直线。那么半平...
上次写完叉积之后感觉意犹未尽,就耗尽了我蒟蒻的所有智商,又去学习了一下二维凸包,发现和叉积一样不(nan)是(dao)太(tu)难(xie),至于为什么不搞三维凸包......因为搞不来啊:sob: 什么是凸包 首先,什么是凸包问题? 在一个平面上有n个点,过某些点做一个多边形能把所有点“包”起来,当这个多边形是凸多边形时,我们就把它叫做“凸包”,如下图: 我们把这些点放在二维坐标系中,...
这几天闲来无事去学习了一下计算几何,发现其实不($sang$)是($xin$)太($bing$)难($kuang$) 今天就重点介绍一下简单的叉积及其简单的运用(毕竟作为蒟蒻,难的搞不来啊) 什么是计算几何? “对几何外形信息的计算机表示、分析和综合”——福雷斯特 其实所谓计算几何,就是用计算机去解决不同维度上的几何问题,而我们要做的,就是设计一套算法,让计算机去分析和解决一系列的几何问...