最新文�? 叠加定理_戴维南定理_诺顿定理 CMOS反相器1_-_电路结构和工作原理 MOSFET和BJT作为开关的区别 车规IC寿命加速试验为什么要做1000h 漫反射积分球原理
\n\n\n```\n\n\n效果\n\n\n\n\n') document.getElementById('render_817').innerHTML = htmlText console.log(htmlText) htmlText = marked.parse('我们将需要解决的几何问题的范围限制在二维平面内，这样就用到了二维计算几何。\n\n要用电脑解平面几何题？数学好的同学们笑了。\n\n我们并不是用计算机算数学卷子上的几何题去了，而是解决一些更加复杂的几何相关问题。\n\n为了解决复杂且抽象的问题，我们一定要选择合适的研究方法。对于计算机来说，给它看几何图形……\n\n我们可以把要研究的图形放在平面直角坐标系或极坐标系下，这样解决问题就会方便很多。\n\n## 前置技能\n\n如并不了解：\n\n- 几何基础\n- 平面直角坐标系\n- 向量（包括向量积）\n- 极坐标与极坐标系\n\n请先阅读 [向量](../math/linear-algebra/vector.md) ?? [极坐标](../math/coordinate.md#平面极坐标系)。\n\n## 图形的记录\n\n### 点\n\n在平面直角坐标系下，点用坐标表示，比如点 $(5,2)$，点 $(-1,0)$ 什么的。\n\n我们记录其横纵坐标值即可。用 `pair` 或开结构体记录均可。\n\n在极坐标系下，用极坐标表示即可。记录其极径与极角。\n\n### 向量\n\n由于向量的坐标表示与点相同，所以只需要像点一样存向量即可（当然点不是向量）。\n\n在极坐标系下，与点同理。\n\n### 线\n\n#### 直线与射线\n\n一般在解数学题时，我们用解析式表示一条直线。有一般式 $Ax+By+C=0$，还有斜截式 $y=kx+b$，还有截距式 $\\dfrac{x}{a}+\\dfrac{y}{b}=1$……用哪种？\n\n这些式子最后都逃不过最后的结果——代入解方程求值。\n\n解方程什么的最讨厌了，有什么好一点的方法吗？\n\n考虑我们只想知道这条直线在哪，它的倾斜程度怎么样。于是用直线上的一个点先大致确定位置，用一个向量表示它的倾斜程度，好了，这条直线确定了。\n\n因此我们记录的是：直线上一点和直线的方向向量。\n\n#### 线段\n\n线段很好记录：只需要记录左右端点即可。\n\n在极坐标系下，记录线是比较麻烦的，因此大多数直线问题都在平面直角坐标系下解决。\n\n### 多边形\n\n开数组按一定顺序记录多边形的每个顶点即可。\n\n特殊地，如果矩形的各边均与某坐标轴平行的话，我们只记录左下角和右上角的顶点即可。\n\n### 曲线\n\n一些特殊曲线，如函数图像等一般记录其解析式。对于圆，直接记录其圆心和半径即可。\n\n## 基本公式\n\n### 正弦定理\n\n在三角形 $\\triangle \\text{ABC}$ 中，若角 $A,B,C$ 所对边分别?? $a,b,c$，则有：\n\n$$\n\\frac{a}{\\sin A}=\\frac{b}{\\sin B}=\\frac{c}{\\sin C}=2R\n$$\n\n其中??$R$ ?? $\\triangle \\text{ABC}$ 的外接圆半径。\n\n### 余弦定理\n\n在三角形 $\\triangle \\text{ABC}$ 中，若角 $A,B,C$ 所对边分别?? $a,b,c$，则有：\n\n$$\n\\begin{aligned}\na^2&=b^2+c^2-2bc\\cos A\\\\\\\\\nb^2&=a^2+c^2-2ac\\cos B\\\\\\\\\nc^2&=a^2+b^2-2ab\\cos C\n\\end{aligned}\n$$\n\n上述公式的证明略。均为人教版高中数学 A 版必修二内容（旧教材为必修五）。\n\n## 基本操作\n\n### 判断一个点在直线的哪边\n\n我们有直线上的一?? $P$ 的直线的方向向量 $\\mathbf v$，想知道某个?? $Q$ 在直线的哪边。\n\n我们利用向量积的性质，算?? $\\overrightarrow {PQ}\\times \\mathbf v$。如果向量积为负，则 $Q$ 在直线上方，如果向量积为 $0$，则 $Q$ 在直线上，如果向量积为正，则 $Q$ 在直线下方。\n\n可以画一下图，用右手定则感受一下。\n\n### 快速排斥实验与跨立实验\n\n我们现在想判断两条线段是否相交。\n\n首先特判一些特殊情况。如果两线段平行，自然不能相交。这种情况通过判断线段所在直线的斜率是否相等即可。\n\n当然，如果两线段重合或部分重合，只需要判断是否有三点共线的情况即可。\n\n如果两线段的交点为其中一条线段的端点，仍然判断是否有三点共线的情况即可。\n\n还有些显然不相交的情况，我们口头上称之为「两条线段离着太远了」。可什么是「离着远」，怎么判断它呢？\n\n规定「一条线段的区域」为以这条线段为对角线的，各边均与某一坐标轴平行的矩形所占的区域，那么可以发现，如果两条线段没有公共区域，则这两条线段一定不相交。\n\n比如有以下两条线段：\n\n![Seg1](./images/2d-seg1.svg)\n\n它们占用的区域是这样的：\n\n![Seg2](./images/2d-seg2.svg)\n\n于是可以快速地判断出来这两条线段不相交。\n\n这就?? **快速排斥实??**。上述情况称?? **未通过快速排斥实??**。\n\n未通过快速排斥实验是两线段无交点?? **充分不必要条??**，我们还需要进一步判断。\n\n因为两线?? $a,b$ 相交??$b$ 线段的两个端点一定分布在 $a$ 线段所在直线两侧；同理??$a$ 线段的两个端点一定分布在 $b$ 线段所在直线两侧。我们可以直接判断一条线段的两个端点相对于另一线段所在直线的位置关系，如果不同，则两线段相交，反之则不相交。如上一节所说，直线与点的位置关系我们可以利用向量积判断。\n\n这就?? **跨立实验**，如果对于两线段 $a,b$??$b$ 线段的两个端点分布在 $a$ 线段所在直线的两侧??**??** $a$ 线段的两个端点分布在 $b$ 线段所在直线的两侧，我们就?? $a,b$ 两线?? **通过了跨立实??**，即两线段相交。\n\n注意到当两条线段共线但不相交时也可以通过跨立实验，因此想要准确判断还需要与快速排斥实验结合。\n\n### 判断一点是否在任意多边形内部\n\n在计算几何中，这个问题被称为 [PIP 问题](https://en.wikipedia.org/wiki/Point_in_polygon)，已经有一些成熟的解决方法，下面依次介绍。\n\n#### 光线投射算法 (Ray casting algorithm)\n\n?? [这里](https://wrf.ecse.rpi.edu/Research/Short_Notes/pnpoly.html) 可以看到最原始的思路。\n\n我们先特判一些特殊情况，比如「这个点离多边形太远了」。考虑一个能够完全覆盖该多边形的最小矩形，如果这个点不在这个矩形范围内，那么这个点一定不在多边形内。这样的矩形很好求，只需要知道多边形横坐标与纵坐标的最小值和最大值，坐标两两组合成四个点，就是这个矩形的四个顶点了。\n\n还有点在多边形的某一边或某顶点上，这种情况十分容易判断（留作课后作业）。\n\n我们考虑以该点为端点引出一条射线，如果这条射线与多边形有奇数个交点，则该点在多边形内部，否则该点在多边形外部，我们简记为 **奇内偶外**。这个算法同样被称为奇偶规则 (Even-odd rule)。\n\n由于 [Jordan curve theorem](https://en.wikipedia.org/wiki/Jordan_curve_theorem)，我们知道，这条射线每次与多边形的一条边相交，就切换一次与多边形的内外关系，所以统计交点数的奇偶即可。\n\n这样的射线怎么取？可以随机取这条射线所在直线的斜率，建议为无理数以避免出现射线与多边形某边重合的情况。\n\n在原版代码中，使用的是记录多边形的数组中最后一个点作为射线上一点，这样统计时，如果出现射线过多边形某边或某顶点时，可以规定射线经过的点同在射线一侧，进而做跨立实验即可。\n\n#### 回转数算?? (Winding number algorithm)\n\n回转数是数学上的概念，是平面内闭合曲线逆时针绕过该点的总次数。很容易发现，当回转数等?? $0$ 的时候，点在曲线外部。这个算法同样被称为非零规则 (Nonzero-rule)。\n\n如何计算呢？我们把该点与多边形的所有顶点连接起来，计算相邻两边夹角的和。注意这里的夹角?? **有方向的**。如果夹角和?? $0$，则这个点在多边形外，否则在多边形内。\n\n### 求两条直线的交点\n\n首先，我们需要确定两条直线相交，只需判断一下两条直线的方向向量是否平行即可。如果方向向量平行，则两条直线平行，交点个数?? $0$。进一步地，若两条直线平行且过同一点，则两直线重合。\n\n那么，问题简化为我们有直?? $AB,CD$ 交于一点，想求出交?? $E$。\n\n如果两直线相交，则交点只有一个，我们记录了直线上的一个点和直线的方向向量，所以我们只需要知道这个点与交点的距离 $l$，再将这个点沿方向向量平?? $l$ 个单位长度即可。\n\n考虑构造三角形，利用正弦定理求?? $l$，可以利用向量积构造出正弦定理。\n\n![Intersection](./images/2d-intersection.svg)\n\n由上图可知，$|\\mathbf a\\times \\mathbf b|=|\\mathbf a||\\mathbf b|\\sin \\beta$??$|\\mathbf u\\times \\mathbf b|=|\\mathbf u||\\mathbf b|\\sin \\theta$。\n\n作商得：\n\n$$\nT=\\frac{|\\mathbf u\\times \\mathbf b|}{|\\mathbf a\\times \\mathbf b|}=\\frac{|\\mathbf u|\\sin \\theta}{|\\mathbf a|\\sin \\beta}\n$$\n\n可以看出??$\\left|\\dfrac{|\\mathbf u|\\sin \\theta}{\\sin \\beta}\\right|=l$。若绝对值内部式子取值为正，代表?? $\\mathbf a$ 方向平移，反之则为反方向。\n\n同时，我们将 $T$ 直接乘上 $\\mathbf a$，就自动出现了直线的单位向量，不需要进行其他消去操作了。\n\n于是，只需要将?? $B$ 减去 $T\\mathbf a$ 即可得出交点。\n\n### 求任意多边形的周长和面积\n\n#### 求任意多边形的周长\n\n直接计算即可，简洁即美德。\n\n#### 求任意多边形的面积\n\n考虑向量积的模的几何意义，我们可以利用向量积完成。\n\n将多边形上的点逆时针标记为 $p_1,p_2,\\cdots ,p_n$，再任选一个辅助点 $O$，记向量 $\\mathbf v_i=p_i-O$，那么这个多边形面积 $S$ 可以表示为：\n\n$$\nS=\\frac{1}{2}\\left|\\sum_{i=1}^n \\mathbf v_i\\times \\mathbf v_{(i\\bmod n)+1}\\right|\n$$\n\n### 圆与直线相关\n\n#### 求直线与圆的交点\n\n首先判断直线与圆的位置关系。如果直线与圆相离则无交点，若相切则可以利用切线求出切点与半径所在直线，之后转化为求两直线交点。\n\n若有两交点，则可以利用勾股定理求出两交点的中点，然后沿直线方向加上半弦长即可。\n\n#### 求两圆交点\n\n首先我们判断一下两个圆的位置关系，如果外离或内含则无交点，如果相切，可以算出两圆心连线的方向向量，然后利用两圆半径计算出平移距离，最后将圆心沿这个方向向量进行平移即可。\n\n如果两圆相交，则必有两个交点，并且关于两圆心连线对称。因此下面只说明一个交点的求法，另一个交点可以用类似方法求出。\n\n我们先将一圆圆心与交点相连，求出两圆心连线与该连线所成角。这样，将两圆心连线的方向向量旋转这个角度，就是圆心与交点相连形成的半径的方向向量了。\n\n最后还是老套路——沿方向向量方向将圆心平移半径长度。\n\n### 极角序\n\n一般来说，这类题需要先枚举一个极点，然后计算出其他点的极坐标，在极坐标系下按极角的顺序解决问题。\n\n#### 例题 [「JOI Spring Camp 2014 Day4」两个人的星座](https://www.ioi-jp.org/camp/2014/2014-sp-tasks/2014-sp-d4.pdf)\n\n平面内有 $n$ 个点，有三种颜色，每个点的颜色是三种中的一种。求不相交的三色三角形对数??$6\\le n\\le 3000$。\n\n#### 题解\n\n如果两个三角形不相交，则一定可以做出两条内公切线，如果相交或内含是做不出内公切线的。三角形的公切线可以类比圆的公切线。\n\n先枚举一个原点，记为 $O$，以这个点为极点，过这个点且?? $x$ 轴平行的直线作为极轴，建立极坐标系，把剩余点按极角由小到大排序。然后统计出在极轴上方和下方的每种点的个数。\n\n然后根据点枚举公切线，记枚举到的点为 $P$，初始时公切线为极轴。开始统计。那么一定存在一条公切线过点 $O$ 和点 $P$。因为公切线与三角形不相交，所以一方选择公切线上方的点，另一方一定选择下方的点。然后利用乘法原理统计方案数即可。\n\n统计完后转公切线，那么点 $P$ 一定改变了相对于公切线的上下位置，而其他点不动，应该只将它的位置信息改变。\n\n这样，可以发现，同一对三角形最终被统计?? $4$ 次，就是同一条公切线会被枚举两次，最后做出的答案应除?? $4$。\n\n分析一下算法复杂度，我们枚举了一个原点，然后对于每一个原点将剩余点排序后线性统计。于是时间复杂度?? $O(n^2\\log n)$。\n\n## 代码编写注意事项\n\n由于计算几何经常进行 `double` 类型的浮点数计算，因此带来了精度问题和时间问题。\n\n有些问题，例如求点坐标均为整数的三角形面积，可以利用其特殊性进行纯整数计算，避免用浮点数影响精度。\n\n由于浮点数计算比整数计算慢，所以需要注意程序的常数因子给时间带来的影响。\n') document.getElementById('render_1102').innerHTML = htmlText console.log(htmlText) htmlText = marked.parse('author: shuzhouliu\n\n三维几何的很多概念与 [二维几何](./2d.md) 是相通的，我们可以用与解决二维几何问题相同的方法来解决三维几何问题。\n\n## 基本概念\n\n点，向量，直线这些概念和二维几何是相似的，这里不再展开。\n\n### 平面\n\n我们可以用平面上的一?? $P_0(x_0,y_0,z_0)$ 和该平面的法向量（即垂直于该平面的向量）$\\boldsymbol{n}$ 来表示一个平靀??\n\n因为 $\\boldsymbol{n}$ 垂直于平面，所?? $\\boldsymbol{n}$ 垂直于该平面内的所有直线。换句话说，?? $\\boldsymbol{n}=(A,B,C)$，则该平面上的点 $P(x,y,z)$ 都满?? $\\boldsymbol{n} \\cdot \\overrightarrow{PP_0} = 0$。\n\n根据向量点积的定义，上式等价于：\n\n$$\nA(x-x_0)+B(y-y_0)+C(z-z_0)=0\n$$\n\n整理后得到：\n\n$$\nAx+By+Cz-(Ax_0+By_0+Cz_0)=0\n$$\n\n?? $D=-(Ax_0+By_0+Cz_0)$，则上式变成 $Ax+By+Cz+D=0$。我们称这个式子为平面的 **一般式**。\n\n## 基本操作\n\n### 直线、平面之间的夹角\n\n运用空间向量的知识，空间中直线、平面之间的夹角可以很快求出。\n\n对于两条异面直线 $a$??$b$，过空间中一?? $P$，作 $a\' \\parallel a$??$b\' \\parallel b\'$，则 $a\'$ ?? $b\'$ 所成的锐角或直角被称为 $a$ ?? $b$ 两条 **异面直线所成的??**。\n\n对于直线 $a$ 和平?? $\\alpha$，若 $a$ ?? $\\alpha$ 相交?? $A$，过 $a$ 上一?? $P$ 引平?? $\\alpha$ 的垂线交 $\\alpha$ ?? $O$，则 $a$ ?? $PO$ 所成的角被称为 **直线与平面所成的??**。特别地，若 $a \\parallel \\alpha$ ?? $a \\subset \\alpha$，则它们之间的夹角为 $0^\\circ$。\n\n对于两个平面 $\\alpha$??$\\beta$，它们的夹角被定义为与两条平面的交线 $l$ 垂直的两条直?? $a,b$（其?? $a \\subset \\alpha$??$b \\subset \\beta$）所成的角。\n\n#### 两直线夹角定义与关系充要条件\n\n- 两直线的方向向量的夹角，叫做两直线的夹角。\n\n有了这个命题，我们就可以得出以下结论：已知两条直?? $l_1, l_2$，它们的方向向量分别?? $s_1 (m_1, n_1, p_1)$??$s_2 (m_2, n_2, p_2)$，设 $\\varphi$ 为两直线夹角，我们可以得?? $\\cos \\varphi = \\dfrac{\\left | m_1m_2+n_1n_2+p_1p_2 \\right |}{\\sqrt{m_1^2+n_1^2+p_1^2}\\sqrt{m_2^2+n_2^2+p_2^2}}$.\n\n- $l_1 \\perp l_2 \\iff m_1m_2 + n_1n_2 + p_1p_2 = 0$\n\n- $l_1 \\parallel l_2 \\iff \\dfrac{m_1}{m_2} = \\dfrac{n_1}{n_2} = \\dfrac{p_1}{p_2}$.\n\n### 三维向量与平面的夹角\n\n当直线与平面不垂直时，直线和它在平面上的投影直线的夹?? $\\varphi$??$\\varphi \\in [0, \\frac{\\pi}{2}]$）称为直线与平面的夹角。\n\n设直线向?? $s(m, n, p)$，平面法线向?? $f(a, b, c)$，那么以下命题成立：\n\n- 角度的正弦值：$\\sin\\varphi = \\dfrac{\\left | am + bn + cp \\right |}{\\sqrt{a^2+b^2+c^2}\\sqrt{m^2+n^2+p^2}}$\n\n- 直线与平面平?? $\\iff am+bn+cp = 0$\n\n- 直线与平面垂?? $\\iff \\dfrac{a}{m} = \\dfrac{b}{n} = \\dfrac{c}{p}$\n\n### 点到平面的距离\n\n### 直线与平面的交点\n\n直接联立直线方程和平面方程即可。\n\n## 立体几何定理\n\n### 三正弦定理\n\n设二面角 $M－AB－N$ 的度数为 $\\alpha$，在平面 $M$ 上有一条射?? $AC$，它和棱 $AB$ 所成角?? $\\beta$，和平面 $N$ 所成的角为 $\\gamma$，则 $\\sin\\gamma = \\sin\\alpha\\cdot\\sin\\beta$。\n\n### 三余弦定理\n\n?? $O$ 为平面上一点，过平面外一?? $B$ 的直?? $BO$ 在面上的射影?? $AO$??$OC$ 为面上的一条直线，那么 $\\angle COB，\\angle AOC，\\angle AOB$ 三角的余弦关系为??$\\cos\\angle BOC=\\cos\\angle AOB\\cdot\\cos\\angle AOC$??$\\angle AOC$??$\\angle AOB$ 只能是锐角）。\n\n## 参考资料\n\n- [3D 空间基础概念之一：点、向量（矢量）和齐次坐标](https://www.cnblogs.com/CodeBlove/articles/1319563.html)\n') document.getElementById('render_1103').innerHTML = htmlText console.log(htmlText) htmlText = marked.parse('## 二维凸包\n\n### 定义\n\n#### 凸多边形\n\n凸多边形是指所有内角大小都?? $[0,\\pi]$ 范围内的 **简单多边形**。\n\n#### 凸包\n\n在平面上能包含所有给定点的最小凸多边形叫做凸包。\n\n其定义为：对于给定集?? $X$，所有包?? $X$ 的凸集的交集 $S$ 被称?? $X$ ?? **凸包**。\n\n实际上可以理解为用一个橡皮筋包含住所有给定点的形态。\n\n凸包用最小的周长围住了给定的所有点。如果一个凹多边形围住了所有的点，它的周长一定不是最小，如下图。根据三角不等式，凸多边形在周长上一定是最优的。\n\n![](./images/ch.png)\n\n### Andrew 算法求凸包\n\n常用的求法有 Graham 扫描法和 Andrew 算法，这里主要介?? Andrew 算法。\n\n#### 性质\n\n该算法的时间复杂度为 $O(n\\log n)$，其?? $n$ 为待求凸包点集的大小，复杂度的瓶颈在于对所有点坐标的双关键字排序。\n\n#### 过程\n\n首先把所有点以横坐标为第一关键字，纵坐标为第二关键字排序。\n\n显然排序后最小的元素和最大的元素一定在凸包上。而且因为是凸多边形，我们如果从一个点出发逆时针走，轨迹总是「左拐」的，一旦出现右拐，就说明这一段不在凸包上。因此我们可以用一个单调栈来维护上下凸壳。\n\n因为从左向右看，上下凸壳所旋转的方向不同，为了让单调栈起作用，我们首先 **升序枚举** 求出下凸壳，然后 **降序** 求出上凸壳。\n\n求凸壳时，一旦发现即将进栈的点（$P$）和栈顶的两个点??$S_1,S_2$，其?? $S_1$ 为栈顶）行进的方向向右旋转，即叉积小?? $0$??$\\overrightarrow{S_2S_1}\\times \\overrightarrow{S_1P}<0$，则弹出栈顶，回到上一步，继续检测，直到 $\\overrightarrow{S_2S_1}\\times \\overrightarrow{S_1P}\\ge 0$ 或者栈内仅剩一个元素为歀??\n\n通常情况下不需要保留位于凸包边上的点，因此上面一段中 $\\overrightarrow{S_2S_1}\\times \\overrightarrow{S_1P}<0$ 这个条件中的??$<$」可以视情况改为 $\\le$，同时后面一个条件应改为 $>$。\n\n#### 实现\n\n```cpp\n// stk[] 是整型，存的是下标\n// p[] 存储向量或点\ntp = 0; // 初始化栈\nstd::sort(p + 1, p + 1 + n); // 对点进行排序\nstk[++tp] = 1;\n// 栈内添加第一个元素，且不更新 used，使?? 1 在最后封闭凸包时也对单调栈更新\nfor (int i = 2; i <= n; ++i) {\n while (tp >= 2 // 下一?? * 操作符被重载为叉积\n && (p[stk[tp]] - p[stk[tp - 1]]) * (p[i] - p[stk[tp]]) <= 0)\n used[stk[tp--]] = 0;\n used[i] = 1; // used 表示在凸壳上\n stk[++tp] = i;\n}\nint tmp = tp; // tmp 表示下凸壳大小\nfor (int i = n - 1; i > 0; --i)\n if (!used[i]) {\n // ↓求上凸壳时不影响下凸壳\n while (tp > tmp && (p[stk[tp]] - p[stk[tp - 1]]) * (p[i] - p[stk[tp]]) <= 0)\n used[stk[tp--]] = 0;\n used[i] = 1;\n stk[++tp] = i;\n }\nfor (int i = 1; i <= tp; ++i) // 复制到新数组中去\n h[i] = p[stk[i]];\nint ans = tp - 1;\n```\n\n```python\nstk = [] # 是整型，存的是下标\np = [] # 存储向量或点\ntp = 0 # 初始化栈\np.sort() # 对点进行排序\nstk[tp] = 1\ntp = tp + 1\n# 栈内添加第一个元素，且不更新 used，使?? 1 在最后封闭凸包时也对单调栈更新\nfor i in range(2, n + 1):\n while tp >= 2 and (p[stk[tp]] - p[stk[tp - 1]]) * (p[i] - p[stk[tp]]) <= 0:\n # 下一?? * 操作符被重载为叉积\n used[stk[tp]] = 0\n tp = tp - 1\n used[i] = 1 # used 表示在凸壳上\n stk[tp] = i\n tp = tp + 1\ntmp = tp # tmp 表示下凸壳大小\nfor i in range(n - 1, 0, -1):\n if used[i] == False:\n # ↓求上凸壳时不影响下凸壳\n while tp > tmp and (p[stk[tp]] - p[stk[tp - 1]]) * (p[i] - p[stk[tp]]) <= 0:\n used[stk[tp]] = 0\n tp = tp - 1\n used[i] = 1\n stk[tp] = i\n tp = tp + 1\nfor i in range(1, tp + 1):\n h[i] = p[stk[i]]\nans = tp - 1\n```\n\n根据上面的代码，最后凸包上?? $\\textit{ans}$ 个元素（额外存储?? $1$ 号点，因?? $h$ 数组中有 $\\textit{ans}+1$ 个元素），并且按逆时针方向排序。周长就是\n\n$$\n\\sum_{i=1}^{\\textit{ans}}\\left|\\overrightarrow{h_ih_{i+1}}\\right|\n$$\n\n### Graham 扫描法\n\n#### 性质\n\n?? Andrew 算法相同，Graham 扫描法的时间复杂度为 $O(n\\log n)$，复杂度瓶颈也在于对所有点排序。\n\n#### 过程\n\n首先找到所有点中，纵坐标最小的一个点 $P$。根据凸包的定义我们知道，这个点一定在凸包上。然后将所有的点以相对于点 P 的极角大小为关键字进行排序。\n\n![](./images/ch1.svg)\n\n?? Andrew 算法类似地，我们考虑从点 $P$ 出发，在凸包上逆时针走，那么我们经过的所有节点一定都是「左拐」的。形式化地说，对于凸包逆时针方向上任意连续经过的三个点 $P_1, P_2, P_3$，一定满?? $\\overrightarrow{P_1 P_2} \\times \\overrightarrow{P_2 P_3} \\ge 0$。\n\n新建一个栈用于存储凸包的信息，先将 $P$ 压入栈中，然后按照极角序依次尝试加入每一个点。如果进栈的?? $P_0$ 和栈顶的两个?? $P_1, P_2$（其?? $P_1$ 为栈顶）行进的方向「右拐」了，那么就弹出栈顶?? $P_1$，不断重复上述过程直至进栈的点与栈顶的两个点满足条件，或者栈中仅剩下一个元素，再将 $P_0$ 压入栈中。\n\n![](./images/ch2.svg)\n\n![](./images/ch3.svg)\n\n???+ note \"代码实现\"\n ```cpp\n struct Point {\n double x, y, ang;\n \n Point operator-(const Point& p) const { return {x - p.x, y - p.y, 0}; }\n } p[MAX];\n \n double dis(Point p1, Point p2) {\n return sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y));\n }\n \n bool cmp(Point p1, Point p2) {\n if (p1.ang == p2.ang) {\n return dis(p1, p[1]) < dis(p2, p[1]);\n }\n return p1.ang < p2.ang;\n }\n \n double cross(Point p1, Point p2) { return p1.x * p2.y - p1.y * p2.x; }\n \n int main() {\n for (int i = 2; i <= n; ++i) {\n if (p[i].y < p[1].y || (p[i].y == p[1].y && p[i].x < p[1].x)) {\n std::swap(p[1], p[i]);\n }\n }\n for (int i = 2; i <= n; ++i) {\n p[i].ang = atan2(p[i].y - p[1].y, p[i].x - p[1].x);\n }\n std::sort(p + 2, p + n + 1, cmp);\n sta[++top] = 1;\n for (int i = 2; i <= n; ++i) {\n while (top >= 2 &&\n cross(p[sta[top]] - p[sta[top - 1]], p[i] - p[sta[top]]) < 0) {\n top--;\n }\n sta[++top] = i;\n }\n return 0;\n }\n ```\n\n## 三维凸包\n\n### 基础知识\n\n> 圆的反演：反演中心为 $O$，反演半径为 $R$，若经过 $O$ 的直线经?? $P$,$P\'$，且 $OP\\times OP\'=R^{2}$，则?? $P$??$P\'$ 关于 $O$ 互为反演。\n\n### 过程\n\n求凸包的过程如下：\n\n- 首先对其微小扰动，避免出现四点共面的情况。\n- 对于一个已知凸包，新增一个点 $P$，将 $P$ 视作一个点光源，向凸包做射线，可以知道，光线的可见面和不可见面一定是由若干条棱隔开的。\n- 将光的可见面删去，并新增由其分割棱与 $P$ 构成的平靀??\n 重复此过程即可，?? [Pick 定理](./pick.md)、欧拉公式（在凸多面体中，其顶点 $V$、边?? $E$ 及面?? $F$ 满足 $V?E+F=2$）和圆的反演，复杂度 $O(n^2)$。[^3d-v]\n\n### 模板题\n\n[P4724【模板】三维凸包](https://www.luogu.com.cn/problem/P4724)\n\n重复上述过程即可得到答案。\n\n???+ note \"代码实现\"\n ```cpp\n --8<-- \"docs/geometry/code/3d/3d_1.cpp\"\n ```\n\n## 练习\n\n- [UVA11626 Convex Hull](https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=78&page=show_problem&problem=2673)\n\n- [「USACO5.1」圈奶牛 Fencing the Cows](https://www.luogu.com.cn/problem/P2742)\n\n- [POJ1873 The Fortified Forest](http://poj.org/problem?id=1873)\n\n- [POJ1113 Wall](http://poj.org/problem?id=1113)\n\n- [「SHOI2012」信用卡凸包](https://www.luogu.com.cn/problem/P3829)\n\n## 参考资料与注释\n\n[^3d-v]: [三维凸包学习小记](https://www.cnblogs.com/xzyxzy/p/10225804.html)\n') document.getElementById('render_1104').innerHTML = htmlText console.log(htmlText) htmlText = marked.parse('author: Chrogeek, frank-xjh, ChungZH, hsfzLZH1, Marcythm, Planet6174, partychicken, i-Yirannn\n\n## 欧氏距离\n\n### 二维空间\n\n#### 定义\n\n欧氏距离，一般也称作欧几里得距离。在平面直角坐标系中，设?? $A,B$ 的坐标分别为 $A(x_1,y_1),B(x_2,y_2)$，则两点间的欧氏距离为：\n\n$$\n\\left | AB \\right | = \\sqrt{\\left ( x_2 - x_1 \\right )^2 + \\left ( y_2 - y_1 \\right )^2}\n$$\n\n#### 解释\n\n举个例子，若在平面直角坐标系中，有两?? $A(6,5),B(2,2)$，通过公式，我们很容易得到 $A,B$ 两点间的欧氏距离：\n\n$$\n\\left | AB \\right | = \\sqrt{\\left ( 2 - 6 \\right )^2 + \\left ( 2 - 5 \\right )^2} = \\sqrt{4^2+3^2} = 5\n$$\n\n除此之外??$P(x,y)$ 到原点的欧氏距离可以用公式表示为：\n\n$$\n|P| = \\sqrt{x^2+y^2}\n$$\n\n### n 维空间\n\n#### 引入\n\n那么，三维空间中两点的欧氏距离公式呢？我们来观察下图。\n\n![dis-3-dimensional](./images/distance-0.png)\n\n我们很容易发现，?? $\\triangle ADC$ 中，$\\angle ADC = 90^\\circ$；在 $\\triangle ACB$ 中，$\\angle ACB = 90^\\circ$。\n\n$$\n\\begin{aligned}\n\\therefore ~ |AB| &= \\sqrt{|AC|^2+|BC|^2} \\\\\\\\\n&= \\sqrt{|AD|^2+|CD|^2+|BC|^2}\n\\end{aligned}\n$$\n\n#### 定义\n\n由此可得，三维空间中欧氏距离的距离公式为：\n\n$$\n\\begin{gathered}\n\\left | AB \\right | = \\sqrt{\\left ( x_2 - x_1 \\right )^2 + \\left ( y_2 - y_1 \\right )^2 + \\left ( z_2 - z_1 \\right )^2} \\\\\\\\\n|P| = \\sqrt{x^2+y^2+z^2}\n\\end{gathered}\n$$\n\n#### 解释\n\n[NOIP2017 提高?? 奶酪](https://uoj.ac/problem/332) 就运用了这一知识，可以作为欧氏距离的例题。\n\n以此类推，我们就得到?? $n$ 维空间中欧氏距离的距离公式：对于 $\\vec A(x_{11}, x_{12}, \\cdots,x_{1n}) ,~ \\vec B(x_{21}, x_{22}, \\cdots,x_{2n})$，有\n\n$$\n\\begin{aligned}\n\\lVert\\overrightarrow{AB}\\rVert &= \\sqrt{\\left ( x_{11} - x_{21} \\right )^2 + \\left ( x_{12} - x_{22} \\right )^2 + \\cdot \\cdot \\cdot +\\left ( x_{1n} - x_{2n} \\right )^2}\\\\\\\\\n&= \\sqrt{\\sum_{i = 1}^{n}(x_{1i} - x_{2i})^2}\n\\end{aligned}\n$$\n\n欧氏距离虽然很有用，但也有明显的缺点。两个整点计算其欧氏距离时，往往答案是浮点型，会存在一定误差。\n\n## 曼哈顿距离\n\n### 定义\n\n在二维空间内，两个点之间的曼哈顿距离（Manhattan distance）为它们横坐标之差的绝对值与纵坐标之差的绝对值之和。设?? $A(x_1,y_1),B(x_2,y_2)$，则 $A,B$ 之间的曼哈顿距离用公式可以表示为：\n\n$$\nd(A,B) = |x_1 - x_2| + |y_1 - y_2|\n$$\n\n### 解释\n\n观察下图：\n\n![manhattan-dis-diff](./images/distance-1.png)\n\n?? $A,B$ 间，黄线、橙线都表示曼哈顿距离，而红线、蓝线表示等价的曼哈顿距离，绿线表示欧氏距离。\n\n同样的例子，在下图中 $A,B$ 的坐标分别为 $A(25,20),B(10,10)$。\n\n![manhattan-dis](./images/distance-2.svg)\n\n通过公式，我们很容易得到 $A,B$ 两点间的曼哈顿距离：\n\n$$\nd(A,B) = |20 - 10| + |25 - 10| = 10 + 15 = 25\n$$\n\n经过推导，我们得?? $n$ 维空间的曼哈顿距离公式为：\n\n$$\n\\begin{aligned}\nd(A,B) &= |x_1 - y_1| + |x_2 - y_2| + \\cdot \\cdot \\cdot + |x_n - y_n|\\\\\\\\\n&= \\sum_{i = 1}^{n}|x_i - y_i|\n\\end{aligned}\n$$\n\n### 性质\n\n除了公式之外，曼哈顿距离还具有以下数学性质：\n\n- **非负??**\n\n 曼哈顿距离是一个非负数。\n\n $d(i,j)\\geq 0$\n\n- **统一??**\n\n 点到自身的曼哈顿距离?? $0$。\n\n $d(i,i) = 0$\n\n- **对称??**\n\n $A$ ?? $B$ ?? $B$ ?? $A$ 的曼哈顿距离相等，且是对称函数。\n\n $d(i,j) = d(j,i)$\n\n- **三角不等??**\n\n 从点 $i$ ?? $j$ 的直接距离不会大于途经的任何其它点 $k$ 的距离。\n\n $d(i,j)\\leq d(i,k)+d(k,j)$\n\n### 例题\n\n[P5098「USACO04OPEN」Cave Cows 3](https://www.luogu.com.cn/problem/P5098)\n\n根据题意，对于式?? $|x_1-x_2|+|y_1-y_2|$，我们可以假?? $x_1 - x_2 \\geq 0$，根?? $y_1 - y_2$ 的符号分成两种情况：\n\n- $(y_1 - y_2 \\geq 0)\\rightarrow |x_1-x_2|+|y_1-y_2|=x_1 + y_1 - (x_2 + y_2)$\n\n- $(y_1 - y_2 < 0)\\rightarrow |x_1-x_2|+|y_1-y_2|=x_1 - y_1 - (x_2 - y_2)$\n\n只要分别求出 $x+y, x-y$ 的最大值和最小值即能得出答案。\n\n??? note \"参考代码\"\n === \"C++\"\n ```cpp\n #include \n using namespace std;\n \n int main() {\n int n, x, y, minx = 0x7fffffff, maxx = 0, miny = 0x7fffffff, maxy = 0;\n scanf(\"%d\", &n);\n for (int i = 1; i <= n; i++) {\n scanf(\"%d%d\", &x, &y);\n minx = min(minx, x + y), maxx = max(maxx, x + y);\n miny = min(miny, x - y), maxy = max(maxy, x - y);\n }\n printf(\"%d\\n\", max(maxx - minx, maxy - miny));\n return 0;\n }\n ```\n \n === \"Python\"\n ```python\n minx = 0x7fffffff; maxx = 0; miny = 0x7fffffff; maxy = 0\n n = int(input())\n for i in range(1, n + 1):\n x, y = map(lambda x:int(x), input().split())\n minx = min(minx, x + y); maxx = max(maxx, x + y)\n miny = min(miny, x - y); maxy = max(maxy, x - y)\n print(max(maxx - minx, maxy - miny))\n ```\n\n其实还有第二种做法，那就是把曼哈顿距离转化为切比雪夫距离求解，最后部分会讲到。\n\n## 切比雪夫距离\n\n### 定义\n\n切比雪夫距离（Chebyshev distance）是向量空间中的一种度量，二个点之间的距离定义为其各坐标数值差的最大值。[^ref1]\n\n在二维空间内，两个点之间的切比雪夫距离为它们横坐标之差的绝对值与纵坐标之差的绝对值的最大值。设?? $A(x_1,y_1),B(x_2,y_2)$，则 $A,B$ 之间的切比雪夫距离用公式可以表示为：\n\n$$\nd(A,B) = \\max(|x_1 - x_2|, |y_1 - y_2|)\n$$\n\n$n$ 维空间中切比雪夫距离的距离公式可以表示为：\n\n$$\n\\begin{aligned}\nd(x,y) &= \\max\\begin{Bmatrix} |x_1 - y_1|,|x_2 - y_2|,\\cdot \\cdot \\cdot,|x_n - y_n|\\end{Bmatrix} \\\\\\\\\n&= \\max\\begin{Bmatrix} |x_i - y_i|\\end{Bmatrix}(i \\in [1, n])\\end{aligned}\n$$\n\n### 解释\n\n仍然是这个例子，下图?? $A,B$ 的坐标分别为 $A(25,20),B(10,10)$。\n\n![Chebyshev-dis](./images/distance-2.svg)\n\n$$\nd(A,B) = \\max(|20 - 10|, |25 - 10|) = \\max(10, 15) = 15\n$$\n\n## 曼哈顿距离与切比雪夫距离的相互转化\n\n### 过程\n\n首先，我们考虑画出平面直角坐标系上所有到原点的曼哈顿距离?? $1$ 的点。\n\n通过公式，我们很容易得到方程 $|x| + |y| = 1$。\n\n将绝对值展开，得?? $4$ ?? 一次函数，分别是：\n\n$$\n\\begin{aligned}\n&y = -x + 1 &(x \\geq 0, y \\geq 0) \\\\\\\\\n&y = x + 1 &(x \\leq 0, y \\geq 0) \\\\\\\\\n&y = x - 1 &(x \\geq 0, y \\leq 0) \\\\\\\\\n&y = -x - 1 &(x \\leq 0, y \\leq 0) \\\\\\\\\n\\end{aligned}\n$$\n\n将这 $4$ 个函数画到平面直角坐标系上，得到一个边长为 $\\sqrt{2}$ 的正方形，如下图所示：\n\n![dis-diff-square-1](./images/distance-3.svg)\n\n正方形边界上所有的点到原点?? 曼哈顿距?? 都是 $1$。\n\n同理，我们再考虑画出平面直角坐标系上所有到原点?? 切比雪夫距离 ?? $1$ 的点。\n\n通过公式，我们知?? $\\max(|x|,|y|)=1$。\n\n我们将式子展开，也同样可以得到可以得到 $4$ ?? 线段，分别是：\n\n$$\n\\begin{aligned}\n&y = 1&(-1\\leq x \\leq 1) \\\\\\\\\n&y = -1&(-1\\leq x \\leq 1) \\\\\\\\\n&x = 1,&(-1\\leq y \\leq 1) \\\\\\\\\n&x = -1,&(-1\\leq y \\leq 1) \\\\\\\\\n\\end{aligned}\n$$\n\n画到平面直角坐标系上，可以得到一个边长为 $2$ 的正方形，如下图所示：\n\n![dis-diff-square-2](./images/distance-4.svg)\n\n正方形边界上所有的点到原点的切比雪夫距离都?? $1$。\n\n将这两幅图对比，我们会神奇地发现：\n\n?? $2$ 个正方形是相似图彀??\n\n### 证明\n\n所以，曼哈顿距离与切比雪夫距离之间会不会有联系呢？\n\n接下来我们简略证明一下：\n\n假设 $A(x_1,y_1),B(x_2,y_2)$，\n\n我们把曼哈顿距离中的绝对值拆开，能够得到四个值，这四个值中的最大值是两个非负数之和，即曼哈顿距离。则 $A,B$ 两点的曼哈顿距离为：\n\n$$\n\\begin{aligned}\nd(A,B)&=|x_1 - x_2| + |y_1 - y_2|\\\\\\\\\n&=\\max\\begin{Bmatrix} x_1 - x_2 + y_1 - y_2, x_1 - x_2 + y_2 - y_1,x_2 - x_1 + y_1 - y_2, x_2 - x_1 + y_2 - y_1\\end{Bmatrix}\\\\\\\\\n&= \\max(|(x_1 + y_1) - (x_2 + y_2)|, |(x_1 - y_1) - (x_2 - y_2)|)\n\\end{aligned}\n$$\n\n我们很容易发现，这就?? $(x_1 + y_1,x_1 - y_1), (x_2 + y_2,x_2 - y_2)$ 两点之间的切比雪夫距离。\n\n所以将每一个点 $(x,y)$ 转化?? $(x + y, x - y)$，新坐标系下的切比雪夫距离即为原坐标系下的曼哈顿距离。\n\n同理??$A,B$ 两点的切比雪夫距离为：\n\n$$\n\\begin{aligned}\nd(A,B)&=\\max\\begin{Bmatrix} |x_1 - x_2|,|y_1 - y_2|\\end{Bmatrix}\\\\\\\\\n&=\\max\\begin{Bmatrix} \\left|\\dfrac{x_1 + y_1}{2}-\\dfrac{x_2 + y_2}{2}\\right|+\\left|\\dfrac{x_1 - y_1}{2}-\\dfrac{x_2 - y_2}{2}\\right|\\end{Bmatrix}\n\\end{aligned}\n$$\n\n而这就是 $(\\dfrac{x_1 + y_1}{2},\\dfrac{x_1 - y_1}{2}), (\\dfrac{x_2 + y_2}{2},\\dfrac{x_2 - y_2}{2})$ 两点之间的曼哈顿距离。\n\n所以将每一个点 $(x,y)$ 转化?? $(\\dfrac{x + y}{2},\\dfrac{x - y}{2})$，新坐标系下的曼哈顿距离即为原坐标系下的切比雪夫距离。\n\n### 结论\n\n- 曼哈顿坐标系是通过切比雪夫坐标系旋?? $45^\\circ$ 后，再缩小到原来的一半得到的。\n- 将一个点 $(x,y)$ 的坐标变?? $(x + y, x - y)$ 后，原坐标系中的曼哈顿距离等于新坐标系中的切比雪夫距离。\n- 将一个点 $(x,y)$ 的坐标变?? $(\\dfrac{x + y}{2},\\dfrac{x - y}{2})$ 后，原坐标系中的切比雪夫距离等于新坐标系中的曼哈顿距离。\n\n碰到求切比雪夫距离或曼哈顿距离的题目时，我们往往可以相互转化来求解。两种距离在不同的题目中有不同的优缺点，应该灵活运用。\n\n### 例题\n\n[P4648「IOI2007」pairs 动物对数](https://www.luogu.com.cn/problem/P4648)（曼哈顿距离转切比雪夫距离）\n\n[P3964「TJOI2013」松鼠聚会](https://www.luogu.com.cn/problem/P3964)（切比雪夫距离转曼哈顿距离）\n\n最后给?? [P5098「USACO04OPEN」Cave Cows 3](https://www.luogu.com.cn/problem/P5098) 的第二种解法：\n\n我们考虑将题目所求的曼哈顿距离转化为切比雪夫距离，即把每个点的坐?? $(x,y)$ 变为 $(x + y, x - y)$。\n\n所求的答案就变?? $\\max\\limits_{i,j\\in n}\\begin{Bmatrix} \\max\\begin{Bmatrix} |x_i - x_j|,|y_i - y_j|\\end{Bmatrix}\\end{Bmatrix}$。\n\n现要使得横坐标之差和纵坐标之差最大，只需要预处理?? $x,y$ 的最大值和最小值即可。\n\n??? note \"参考代码\"\n === \"C++\"\n ```cpp\n #include \n using namespace std;\n \n int main() {\n int n, x, y, a, b, minx = 0x7fffffff, maxx = 0, miny = 0x7fffffff, maxy = 0;\n scanf(\"%d\", &n);\n for (int i = 1; i <= n; i++) {\n scanf(\"%d%d\", &a, &b);\n x = a + b, y = a - b;\n minx = min(minx, x), maxx = max(maxx, x);\n miny = min(miny, y), maxy = max(maxy, y);\n }\n printf(\"%d\\n\", max(maxx - minx, maxy - miny));\n return 0;\n }\n ```\n \n === \"Python\"\n ```python\n minx = 0x7fffffff; maxx = 0; miny = 0x7fffffff; maxy = 0\n n = int(input())\n for i in range(1, n + 1):\n a, b = map(lambda x:int(x), input().split())\n x = a + b; y = a - b\n minx = min(minx, x); maxx = max(maxx, x)\n miny = min(miny, y); maxy = max(maxy, y)\n print(max(maxx - minx, maxy - miny))\n ```\n\n对比两份代码，我们又能够发现，两种不同的思路，写出来的代码却是完全等价的，是不是很神奇呢？当然，更高深的东西需要大家另行研究。\n\n## $L_m$ 距离\n\n一般地，我们定义平面上两点 $A(x_1, y_1)$??$B(x_2, y_2)$ 之间?? $L_m$ 距离为\n\n$d(L_m) = (|x_1-x_2|^m+|y_1-y_2|^m)^{\\frac{1}{m}}$\n\n特殊的，$L_2$ 距离就是欧几里得距离??$L_1$ 距离就是曼哈顿距离。\n\n## 汉明距离\n\n汉明距离是两个字符串之间的距离，它表示两个长度相同的字符串对应位字符不同的数量\n\n我们可以简单的认为对两个串进行异或运算，结果为 1 的数量就是两个串的汉明距离。\n\n## 参考资料与链接\n\n1. [浅谈三种常见的距离算法](https://www.luogu.com.cn/blog/xuxing/Distance-Algorithm)，感谢作?? xuxing 的授权。\n\n[^ref1]: [切比雪夫距离 - 维基百科，自由的百科全书](https://zh.wikipedia.org/wiki/%E5%88%87%E6%AF%94%E9%9B%AA%E5%A4%AB%E8%B7%9D%E7%A6%BB)\n') document.getElementById('render_1105').innerHTML = htmlText console.log(htmlText) htmlText = marked.parse('author: wjy-yy, Ir1d, Xeonacid\n\n## 定义\n\n### 半平面\n\n一条直线和直线的一侧。半平面是一个点集，因此是一条直线和直线的一侧构成的点集。当包含直线时，称为闭半平面；当不包含直线时，称为开半平靀??\n\n解析式一般为 $Ax+By+C\\ge 0$。\n\n在计算几何中用向量表示，整个题统一以向量的左侧或右侧为半平靀??\n\n![半平面](./images/hpi1.svg)\n\n### 半平面交\n\n半平面交是指多个半平面的交集。因为半平面是点集，所以点集的交集仍然是点集。在平面直角坐标系围成一个区域。\n\n这就很像普通的线性规划问题了，得到的半平面交就是线性规划中的可行域。一般情况下半平面交是有限的，经常考察面积等问题的解决。\n\n它可以理解为向量集中每一个向量的右侧的交，或者是下面方程组的解。\n\n$$\n\\begin{cases}\nA_1x+B_1y+C\\ge 0\\\\\\\\\nA_2x+B_2y+C\\ge 0\\\\\\\\\n\\cdots\n\\end{cases}\n$$\n\n### 多边形的核\n\n如果一个点集中的点与多边形上任意一点的连线与多边形没有其他交点，那么这个点集被称为多边形的核。\n\n把多边形的每条边看成是首尾相连的向量，那么这些向量在多边形内部方向的半平面交就是多边形的核。\n\n## 解法 - S&I 算法\n\n### 极角排序\n\nC 语言有一个库函数叫做 `atan2(double y,double x)`，可以返?? $\\theta\\in (-\\pi,\\pi]$??$\\theta =\\arctan \\frac{y}{x}$。\n\n直接以向量为自变量，调用这个函数，以返回值为关键字排序，得到新的边（向量）集。\n\n排序时，如果遇到共线向量（且方向相同），则取靠近可行域的一个。比如两个向量的极角相同，而我们要的是向量的左侧半平面，那么我们只需要保留左侧的向量。判断方法是取其中一个向量的起点或终点与另一个比较，检查是在左边还是在右边。\n\n### 维护单调队列\n\n因为半平面交是一个凸多边形，所以需要维护一个凸壳。因为后来加入的只可能会影响最开始加入的或最后加入的边（此时凸壳连通），只需要删除队首和队尾的元素，所以需要用单调队列。\n\n我们遍历排好序了的向量，并维护另一个交点数组。当单队中元素超?? 2 个时，他们之间就会产生交点。\n\n对于当前向量，如果上一个交点在这条向量表示的半平面交的 **异侧**，那么上一条边就没有意义了。\n\n![单调队列](./images/hpi2.svg)\n\n如上图，假设取向量左侧半平面。极角排序后，遍历顺序应该是 $\\vec a\\to\\vec b\\to\\vec c$。当 $\\vec a$ ?? $\\vec b$ 入队时，在交点数组里会产生一个点 $D$（交点数组保存队列中相同下标的向量与前一向量的交点）。\n\n接下来枚举到 $\\vec c$ 时，发现 $D$ ?? $\\vec c$ 的右侧。而因?? **产生** $D$ **的向量的极角一定比** $\\vec c$ **要小**，所以产?? $D$ 的向量（?? $\\vec b$）就对半平面交没有影响了。\n\n还有一种可能的情况是快结束的时候，新加入的向量会从队首开始造成影响。\n\n![队首影响](./images/hpi7.svg)\n\n仍然假设取向量左侧半平面。加入向?? $\\vec f$ 之后，第一个交?? $G$ 就在 $\\vec f$ 的右侧，我们把上面的判断标准逆过来看，就知道此时应该删除向量 $\\vec a$，也?? **队首** 的向量。\n\n最后用队首的向量排除一下队尾多余的向量。因为队首的向量会被后面的约束，而队尾的向量不会。此时它们围成了一个环，因此队首的向量就可以约束队尾的向量。\n\n### 得到半平面交\n\n如果半平面交是一个凸 $n$ 边形，最后在交点数组里会得到 $n$ 个点。我们再把它们首尾相连，就是一个统一方向（顺或逆时针）?? $n$ 多边彀??\n\n此时就可以用三角剖分求面积了。（求面积是最基础的考法）\n\n偶尔会出现半平面交不存在或面积为 0 的情况，注意考虑边界。\n\n### 注意事项\n\n当出现一个可以把队列里的点全部弹出去的向量（即所有队列里的点都在该向量的右侧），则我?? **必须** 先处理队尾，再处理队首。因此在循环中，我们先枚?? `--r;` 的部分，再枚?? `++l;` 的部分，才不会错。原因如下。\n\n![](./images/hpi4.svg)\n\n一般情况下，我们在队列（队列顺序为 $\\left\\{\\vec{u},\\vec{v}\\right\\}$）后面加一条边（向?? $\\vec w$），会产生一个交?? $N$，缩?? $\\vec{v}$ 后面的范围。\n\n![](./images/hpi5.svg)\n\n但是毕竟每次操作都是一般的，因此可能会有把 $M$ 点「挤出去」的情况。\n\n![](./images/hpi6.svg)\n\n如果此时出现了向?? $\\vec a$，使?? $M$ ?? $\\vec a$ 的右侧，那么 $M$ 就要出队了。此时如果从队首枚举 `++l`，显然是扩大了范围。实际上 $M$ 点是?? $\\vec u$ ?? $\\vec v$ 共同构成的，因此需要考虑影响到现有进程的?? $\\vec u$ 还是 $\\vec v$。而因为我们在极角排序后，向量是逆时针顺序，所?? $\\vec v$ 的影响要更大一些。\n\n就如上图，如?? $M$ 确认?? $\\vec a$ 的右侧，那么此时 $\\vec v$ 的影响一定不会对半平面交的答案作出任何贡献。\n\n而我们排除队首的原因?? **当前向量的限制比队首向量要大**，这个条件的前提是队列里有不止两个线段（向量），不然就会出现上面的情况。\n\n所以一定要先排除队尾再排除队首。\n\n ```cpp\nfriend bool operator<(seg x, seg y) {\n db t1 = atan2((x.b - x.a).y, (x.b - x.a).x);\n db t2 = atan2((y.b - y.a).y, (y.b - y.a).x); // 求极角\n if (fabs(t1 - t2) > eps) // 如果极角不等\n return t1 < t2;\n return (y.a - x.a) * (y.b - x.a) >\n eps; // 判断向量x在y的哪边，令最靠左的排在最左边\n}\n```\n\n ```cpp\n// pnt its(seg a,seg b)表示求线段a,b的交点\n// s[]是极角排序后的向量\n// q[]是向量队列\n// t[i]是s[i-1]与s[i]的交点\n// 【码风】队列的范围??(l,r]\n// 求的是向量左侧的半平面\nint l = 0, r = 0;\nfor (int i = 1; i <= n; ++i)\n if (s[i] != s[i - 1]) {\n // 注意要先检查队尾\n while (r - l > 1 && (s[i].b - t[r]) * (s[i].a - t[r]) >\n eps) // 如果上一个交点在向量右侧则弹出队尾\n --r;\n while (r - l > 1 && (s[i].b - t[l + 2]) * (s[i].a - t[l + 2]) >\n eps) // 如果第一个交点在向量右侧则弹出队首\n ++l;\n q[++r] = s[i];\n if (r - l > 1) t[r] = its(q[r], q[r - 1]); // 求新交点\n }\nwhile (r - l > 1 &&\n (q[l + 1].b - t[r]) * (q[l + 1].a - t[r]) > eps) // 注意删除多余元素\n --r;\nt[r + 1] = its(q[l + 1], q[r]); // 再求出新的交点\n++r;\n// 这里不能在t里面++r需要注意一下……\n```\n\n## 练习\n\n[POJ 2451 Uyuw\'s Concert](http://poj.org/problem?id=2451) 注意边界\n\n[POJ 1279 Art Gallery](http://poj.org/problem?id=1279) 求多边形的核\n\n[「CQOI2006」凸多边形](https://www.luogu.com.cn/problem/P4196)\n') document.getElementById('render_1106').innerHTML = htmlText console.log(htmlText) htmlText = marked.parse('## 引入\n\n给定 $n$ 个二维平面上的点，求一组欧几里得距离最近的点对。\n\n下面我们介绍一种时间复杂度?? $O(n\\log n)$ 的分治算法来解决这个问题。该算法?? 1975 年由 [Franco P. Preparata](https://en.wikipedia.org/wiki/Franco_P._Preparata) 提出，Preparata ?? [Michael Ian Shamos](https://en.wikipedia.org/wiki/Michael_Ian_Shamos) 证明了该算法在决策树模型下是最优的。\n\n## 过程\n\n与常规的分治算法一样，我们将这个有 $n$ 个点的集合拆分成两个大小相同的集?? $S_1, S_2$，并不断递归下去。但是我们遇到了一个难题：如何合并？即如何求出一个点?? $S_1$ 中，另一个点?? $S_2$ 中的最近点对？这里我们先假设合并操作的时间复杂度为 $O(n)$，可知算法总复杂度?? $T(n) = 2T(\\frac{n}{2}) + O(n) = O(n\\log n)$。\n\n我们先将所有点按照 $x_i$ 为第一关键字??$y_i$ 为第二关键字排序，并以点 $p_m (m = \\lfloor \\frac{n}{2} \\rfloor)$ 为分界点，拆分点集为 $A_1,A_2$：\n\n$$\n\\begin{aligned}\nA_1 &= \\{p_i \\ \\big | \\ i = 0 \\ldots m \\}\\\\\\\\\nA_2 &= \\{p_i \\ \\big | \\ i = m + 1 \\ldots n-1 \\}\n\\end{aligned}\n$$\n\n并递归下去，求出两点集各自内部的最近点对，设距离为 $h_1,h_2$，取较小值设?? $h$。\n\n现在该合并了！我们试图找到这样的一组点对，其中一个属?? $A_1$，另一个属?? $A_2$，且二者距离小?? $h$。因此我们将所有横坐标?? $x_m$ 的差小于 $h$ 的点放入集合 $B$：\n\n$$\nB = \\{ p_i \\ \\big | \\ \\lvert x_i - x_m \\rvert < h \\}\n$$\n\n结合图像，直?? $m$ 将点分成了两部分??$m$ 左侧?? $A_1$ 点集，右侧为?? $A_2$ 点集。\n\n再根?? $B = \\{ p_i \\ \\big | \\ \\lvert x_i - x_m \\rvert < h \\}$ 规则，得到绿色点组成?? $B$ 点集??![nearest-points1](./images/nearest-points1.png)\n\n对于 $B$ 中的每个?? $p_i$，我们当前目标是找到一个同样在 $B$ 中、且到其距离小于 $h$ 的点。为了避免两个点之间互相考虑，我们只考虑那些纵坐标小?? $y_i$ 的点。显然对于一个合法的?? $p_j$??$y_i - y_j$ 必须小于 $h$。于是我们获得了一个集?? $C(p_i)$：\n\n$$\nC(p_i) = \\{ p_j\\ \\big |\\ p_j \\in B,\\ y_i - h < y_j \\le y_i \\}\n$$\n\n在点?? $B$ 中选一?? $p_i$，根?? $C(p_i) = \\{ p_j\\ \\big |\\ p_j \\in B,\\ y_i - h < y_j \\le y_i \\}$ 的规则，得到了由红色方框内的黄色点组成的 $C$ 点集。\n\n![nearest-points2](./images/nearest-points2.png)\n\n如果我们?? $B$ 中的点按?? $y_i$ 排序??$C(p_i)$ 将很容易得到，即紧邻 $p_i$ 的连续几个点。\n\n由此我们得到了合并的步骤：\n\n1. 构建集合 $B$。\n2. ?? $B$ 中的点按?? $y_i$ 排序。通常做法?? $O(n\\log n)$，但是我们可以改变策略优化到 $O(n)$（下文讲解）。\n3. 对于每个 $p_i \\in B$ 考虑 $p_j \\in C(p_i)$，对于每?? $(p_i,p_j)$ 计算距离并更新答案（当前所处集合的最近点对）。\n\n注意到我们上文提到了两次排序，因为点坐标全程不变，第一次排序可以只在分治开始前进行一次。我们令每次递归返回当前点集?? $y_i$ 排序的结果，对于第二次排序，上层直接使用下层的两个分别排序过的点集归并即可。\n\n似乎这个算法仍然不优??$|C(p_i)|$ 将处?? $O(n)$ 数量级，导致总复杂度不对。其实不然，其最大大小为 $7$，我们给出它的证明：\n\n## 复杂度证明\n\n我们已经了解到，$C(p_i)$ 中的所有点的纵坐标都在 $(y_i-h,y_i]$ 范围内；?? $C(p_i)$ 中的所有点，和 $p_i$ 本身，横坐标都在 $(x_m-h,x_m+h)$ 范围内。这构成了一?? $2h \\times h$ 的矩彀??\n\n我们再将这个矩形拆分为两?? $h \\times h$ 的正方形，不考虑 $p_i$，其中一个正方形中的点为 $C(p_i) \\cap A_1$，另一个为 $C(p_i) \\cap A_2$，且两个正方形内的任意两点间距离大于 $h$。（因为它们来自同一下层递归）\n\n我们将一?? $h \\times h$ 的正方形拆分为四?? $\\frac{h}{2} \\times \\frac{h}{2}$ 的小正方彀??可以发现，每个小正方形中最多有 $1$ 个点：因为该小正方形中任意两点最大距离是对角线的长度，即 $\\frac{h}{\\sqrt 2}$，该数小?? $h$。\n\n![nearest-points3](./images/nearest-points3.png)\n\n由此，每个正方形中最多有 $4$ 个点，矩形中最多有 $8$ 个点，去?? $p_i$ 本身??$\\max(C(p_i))=7$。\n\n## 实现\n\n我们使用一个结构体来存储点，并定义用于排序的函数对象：\n\n```cpp\n struct pt {\n int x, y, id;\n };\n \n struct cmp_x {\n bool operator()(const pt& a, const pt& b) const {\n return a.x < b.x || (a.x == b.x && a.y < b.y);\n }\n };\n \n struct cmp_y {\n bool operator()(const pt& a, const pt& b) const { return a.y < b.y; }\n };\n \n int n;\n vector a;\n```\n\n为了方便实现递归，我们引?? `upd_ans()` 辅助函数来计算两点间距离并尝试更新答案：\n\n```cpp\n double mindist;\n int ansa, ansb;\n \n void upd_ans(const pt& a, const pt& b) {\n double dist =\n sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y) + .0);\n if (dist < mindist) mindist = dist, ansa = a.id, ansb = b.id;\n }\n```\n\n下面是递归本身：假设在调用?? `a[]` 已按 $x_i$ 排序。如?? $r-l$ 过小，使用暴力算法计?? $h$，终止递归。\n\n我们使用 `std::inplace_merge()` 来执行归并排序，并创建辅助缓冲区 `t[]`??$B$ 存储在其中。\n\n```cpp\n void rec(int l, int r) {\n if (r - l <= 3) {\n for (int i = l; i <= r; ++i)\n for (int j = i + 1; j <= r; ++j) upd_ans(a[i], a[j]);\n sort(a + l, a + r + 1, &cmp_y);\n return;\n }\n \n int m = (l + r) >> 1;\n int midx = a[m].x;\n rec(l, m), rec(m + 1, r);\n inplace_merge(a + l, a + m + 1, a + r + 1, &cmp_y);\n \n static pt t[MAXN];\n int tsz = 0;\n for (int i = l; i <= r; ++i)\n if (abs(a[i].x - midx) < mindist) {\n for (int j = tsz - 1; j >= 0 && a[i].y - t[j].y < mindist; --j)\n upd_ans(a[i], t[j]);\n t[tsz++] = a[i];\n }\n }\n```\n\n在主函数中，这样开始递归即可：\n\n```cpp\n sort(a, a + n, &cmp_x);\n mindist = 1E20;\n rec(0, n - 1);\n```\n\n## 推广：平面最小周长三角形\n\n上述算法有趣地推广到这个问题：在给定的一组点中，选择三个点，使得它们两两的距离之和最小。\n\n算法大体保持不变，每次尝试找到一个比当前答案周长 $d$ 更小的三角形，将所有横坐标?? $x_m$ 的差小于 $\\frac{d}{2}$ 的点放入集合 $B$，尝试更新答案。（周长?? $d$ 的三角形的最长边小于 $\\frac{d}{2}$）\n\n## 非分治算法\n\n### 过程\n\n其实，除了上面提到的分治算法，还有另一种时间复杂度同样?? $O(n \\log n)$ 的非分治算法。\n\n我们可以考虑一种常见的统计序列的思想：对于每一个元素，将它和它的左边所有元素的贡献加入到答案中。平面最近点对问题同样可以使用这种思想。\n\n具体地，我们把所有点按照 $x_i$ 为第一关键字??$y_i$ 为第二关键字排序，并建立一个以 $y_i$ 为第一关键字??$x_i$ 为第二关键字排序?? multiset。对于每一个位?? $i$，我们执行以下操作：\n\n1. 将所有满?? $x_i - x_j >= d$ 的点从集合中删除。它们不会再对答案有贡献。\n2. 对于集合内满?? $\\lvert y_i - y_j \\rvert < d$ 的所有点，统计它们和 $p_i$ 的距离。\n3. ?? $p_i$ 插入到集合中。\n\n由于每个点最多会被插入和删除一次，所以插入和删除点的时间复杂度为 $O(n \\log n)$，而统计答案部分的时间复杂度证明与分治算法的时间复杂度证明方法类似，读者不妨一试。\n\n### 实现\n\n```cpp\n #include \n #include \n #include \n #include \n const int N = 200005;\n int n;\n double ans = 1e20;\n \n struct point {\n double x, y;\n \n point(double x = 0, double y = 0) : x(x), y(y) {}\n };\n \n struct cmp_x {\n bool operator()(const point &a, const point &b) const {\n return a.x < b.x || (a.x == b.x && a.y < b.y);\n }\n };\n \n struct cmp_y {\n bool operator()(const point &a, const point &b) const { return a.y < b.y; }\n };\n \n void upd_ans(const point &a, const point &b) {\n double dist = sqrt(pow((a.x - b.x), 2) + pow((a.y - b.y), 2));\n if (ans > dist) ans = dist;\n }\n \n point a[N];\n std::multiset s;\n \n int main() {\n scanf(\"%d\", &n);\n for (int i = 0; i < n; i++) scanf(\"%lf%lf\", &a[i].x, &a[i].y);\n std::sort(a, a + n, cmp_x());\n for (int i = 0, l = 0; i < n; i++) {\n while (l < i && a[i].x - a[l].x >= ans) s.erase(s.find(a[l++]));\n for (auto it = s.lower_bound(point(a[i].x, a[i].y - ans));\n it != s.end() && it->y - a[i].y < ans; it++)\n upd_ans(*it, a[i]);\n s.insert(a[i]);\n }\n printf(\"%.4lf\", ans);\n return 0;\n }\n```\n\n## 期望线性做法\n\n其实，除了上面提到的时间复杂度为 $O(n \\log n)$ 的做法，还有一?? **期望** 复杂度为 $O(n)$ 的算法。\n\n首先将点?? [随机打乱](../misc/random.md#shuffle)，我们将维护前缀点集的答案。考虑从前 $i - 1$ 个点求出?? $i$ 个点的答案。\n\n记前 $i - 1$ 个点的最近点对距离为 $s$，我们将平面?? $s$ 为边长划分为若干个网格，并存下每个网格内的点（使?? [哈希表](../ds/hash.md)），\n然后检查第 $i$ 个点所在网格的周围九个网格中的所有点，并更新答案。注意到需检查的点的个数?? $O(1)$ 的，因为?? $i - 1$ 个点的最近点对距离为 $s$，\n从而每个网格不超过 4 个点。\n\n如果这一过程中，答案被更新，我们就重构网格图，否则不重构。在?? $i$ 个点中，最近点对包?? $i$ 的概率为 $O\\left(\\frac{1}{i}\\right)$，\n而重构网格的代价?? $O(i)$，从而第 $i$ 个点的期望代价为 $O(1)$。于是对?? $n$ 个点，该算法期望?? $O(n)$。\n\n## 习题\n\n- [UVA 10245 \"The Closest Pair Problem\"\\[难度：低\\]](https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1186)\n- [SPOJ #8725 CLOPPAIR \"Closest Point Pair\"\\[难度：低\\]](https://www.spoj.com/problems/CLOPPAIR/)\n- [CODEFORCES Team Olympiad Saratov - 2011 \"Minimum amount\"\\[难度：中\\]](http://codeforces.com/contest/120/problem/J)\n- [SPOJ #7029 CLOSEST \"Closest Triple\"\\[难度：中\\]](https://www.spoj.com/problems/CLOSEST/)\n- [Google Code Jam 2009 Final \"Min Perimeter\"\\[难度：中\\]](https://web.archive.org/web/20230329043437/https://codingcompetitions.withgoogle.com/codejam/round/0000000000432ad5/0000000000433195)\n\n***\n\n## 参考资料与拓展阅读\n\n**本页面中的分治算法部分主要译自博?? [Нахождение пары ближайших точек](http://e-maxx.ru/algo/nearest_points) 与其英文翻译?? [Finding the nearest pair of points](https://github.com/e-maxx-eng/e-maxx-eng/blob/master/src/geometry/nearest_points.md)。其中俄文版版权协议?? Public Domain + Leave a Link；英文版版权协议?? CC-BY-SA 4.0??**\n\n[知乎专栏：计算几?? - 最近点对问题](https://zhuanlan.zhihu.com/p/74905629)\n') document.getElementById('render_1109').innerHTML = htmlText console.log(htmlText) htmlText = marked.parse('## Pick 定理\n\nPick 定理：给定顶点均为整点的简单多边形，皮克定理说明了其面?? ${\\displaystyle A}$ 和内部格点数?? ${\\displaystyle i}$、边上格点数?? ${\\displaystyle b}$ 的关系：${\\displaystyle A=i+{\\frac {b}{2}}-1}$。\n\n具体证明：[Pick\'s theorem](https://en.wikipedia.org/wiki/Pick%27s_theorem)\n\n它有以下推广：\n\n- 取格点的组成图形的面积为一单位。在平行四边形格点，皮克定理依然成立。套用于任意三角形格点，皮克定理则是 ${\\displaystyle A=2 \\times i+b-2}$。\n- 对于非简单的多边?? ${\\displaystyle P}$，皮克定?? ${\\displaystyle A=i+{\\frac {b}{2}}-\\chi (P)}$，其?? ${\\displaystyle \\chi (P)}$ 表示 ${\\displaystyle P}$ ?? **欧拉特征??**。\n- 高维推广：Ehrhart 多项式\n- 皮克定理?? **欧拉公式**??${\\displaystyle V-E+F=2}$）等价。\n\n## 一道例?? ([POJ 1265](http://poj.org/problem?id=1265))\n\n### 题目大意\n\n在直角坐标系中，一个机器人从任意点出发进行 $\\textit{n}$ 次移动，每次向右移动 $\\textit{dx}$，向上移?? $\\textit{dy}$，最后会形成一个平面上的封闭简单多边形，求边上的点的数量，多边形内的点的数量，多边形面积。\n\n### 题解\n\n这道题目其实用了以下三个知识：\n\n- 以整点为顶点的线段，如果?? $\\textit{dx}$ ?? $\\textit{dy}$ 都不?? $0$，经过的格点数是 $\\gcd(\\textit{dx}, \\textit{dy}) + 1$，当然，如果要算一整个图形的，多加的点会被上一条边计算，也就不需要加了。那么一条边覆盖的点的个数为 $\\gcd(\\textit{dx},\\textit{dy})$，其中，$\\textit{dx},\\textit{dy}$ 分别为线段横向占的点数和纵向占的点数。如?? $\\textit{dx}$ ?? $\\textit{dy}$ ?? $0$，则覆盖的点数为 $\\textit{dy}$ **??** $\\textit{dx}$。\n- Pick 定理：平面上以整点为顶点的简单多边形的面?? = 边上的点??/2 + 内部的点?? + 1。\n- 任意一个多边形的面积等于按顺序求相邻两个点与原点组成的向量的叉积之和的一半（这个也可以通过顺时针定积分求得）。\n\n```cpp\n --8<-- \"docs/geometry/code/pick/pick_1.cpp\"\n```\n') document.getElementById('render_1110').innerHTML = htmlText console.log(htmlText) htmlText = marked.parse('author: Ir1d, TianyiQ\n\n## 引入\n\n随机增量算法是计算几何的一个重要算法，它对理论知识要求不高，算法时间复杂度低，应用范围广大。\n\n增量?? (Incremental Algorithm) 的思想与第一数学归纳法类似，它的本质是将一个问题化为规模刚好小一层的子问题。解决子问题后加入当前的对象。写成递归式是：\n\n$$\nT(n)=T(n-1)+g(n)\n$$\n\n增量法形式简洁，可以应用于许多的几何题目中。\n\n增量法往往结合随机化，可以避免最坏情况的出现。\n\n## 最小圆覆盖问题\n\n### 题意描述\n\n在一个平面上?? $n$ 个点，求一个半径最小的圆，能覆盖所有的点。\n\n### 过程\n\n假设?? $O$ 是前 $i-1$ 个点的最小覆盖圆，加入第 $i$ 个点，如果在圆内或边上则什么也不做。否则，新得到的最小覆盖圆肯定经过?? $i$ 个点。\n\n然后以第 $i$ 个点为基础（半径为 $0$），重复以上过程依次加入?? $j$ 个点，若?? $j$ 个点在圆外，则最小覆盖圆必经过第 $j$ 个点。\n\n重复以上步骤。（因为最多需要三个点来确定这个最小覆盖圆，所以重复三次）\n\n遍历完所有点之后，所得到的圆就是覆盖所有点得最小圆。\n\n### 性质\n\n**时间复杂??** $O(n)$，证明详见参考资料。\n\n**空间复杂??** $O(n)$\n\n### 实现\n\n??? note \"代码实现\"\n ```cpp\n #include \n #include \n #include \n #include \n #include \n \n using namespace std;\n \n int n;\n double r;\n \n struct point {\n double x, y;\n } p[100005], o;\n \n double sqr(double x) { return x * x; }\n \n double dis(point a, point b) { return sqrt(sqr(a.x - b.x) + sqr(a.y - b.y)); }\n \n bool cmp(double a, double b) { return fabs(a - b) < 1e-8; }\n \n point geto(point a, point b, point c) {\n double a1, a2, b1, b2, c1, c2;\n point ans;\n a1 = 2 * (b.x - a.x), b1 = 2 * (b.y - a.y),\n c1 = sqr(b.x) - sqr(a.x) + sqr(b.y) - sqr(a.y);\n a2 = 2 * (c.x - a.x), b2 = 2 * (c.y - a.y),\n c2 = sqr(c.x) - sqr(a.x) + sqr(c.y) - sqr(a.y);\n if (cmp(a1, 0)) {\n ans.y = c1 / b1;\n ans.x = (c2 - ans.y * b2) / a2;\n } else if (cmp(b1, 0)) {\n ans.x = c1 / a1;\n ans.y = (c2 - ans.x * a2) / b2;\n } else {\n ans.x = (c2 * b1 - c1 * b2) / (a2 * b1 - a1 * b2);\n ans.y = (c2 * a1 - c1 * a2) / (b2 * a1 - b1 * a2);\n }\n return ans;\n }\n \n int main() {\n scanf(\"%d\", &n);\n for (int i = 1; i <= n; i++) scanf(\"%lf%lf\", &p[i].x, &p[i].y);\n for (int i = 1; i <= n; i++) swap(p[rand() % n + 1], p[rand() % n + 1]);\n o = p[1];\n for (int i = 1; i <= n; i++) {\n if (dis(o, p[i]) < r || cmp(dis(o, p[i]), r)) continue;\n o.x = (p[i].x + p[1].x) / 2;\n o.y = (p[i].y + p[1].y) / 2;\n r = dis(p[i], p[1]) / 2;\n for (int j = 2; j < i; j++) {\n if (dis(o, p[j]) < r || cmp(dis(o, p[j]), r)) continue;\n o.x = (p[i].x + p[j].x) / 2;\n o.y = (p[i].y + p[j].y) / 2;\n r = dis(p[i], p[j]) / 2;\n for (int k = 1; k < j; k++) {\n if (dis(o, p[k]) < r || cmp(dis(o, p[k]), r)) continue;\n o = geto(p[i], p[j], p[k]);\n r = dis(o, p[i]);\n }\n }\n }\n printf(\"%.10lf\\n%.10lf %.10lf\", r, o.x, o.y);\n return 0;\n }\n ```\n\n## 练习\n\n[最小圆覆盖](https://www.luogu.com.cn/problem/P1742)\n\n[「HNOI2012」射箭](https://www.luogu.com.cn/problem/P3222)\n\n[CodeForces 442E](https://codeforces.com/problemset/problem/442/E)\n\n## 参考资料与扩展阅读\n\n\n\n\n\n\n\n\n') document.getElementById('render_1111').innerHTML = htmlText console.log(htmlText) htmlText = marked.parse('本页面将主要介绍旋转卡壳。\n\n## 引入\n\n旋转卡壳（Rotating Calipers，也称「旋转卡尺」）算法，在凸包算法的基础上，通过枚举凸包上某一条边的同时维护其他需要的点，能够在线性时间内求解如凸包直径、最小矩形覆盖等和凸包性质相关的问题。\n\n???+ note \"算法中文名称\"\n 该算法比较常见的中文名是「旋转卡壳」。可以理解为：根据我们枚举的边，可以从每个维护的点画出一条或平行或垂直的直线，为了确保对于当前枚举的边的最优性，我们的任务就是使这些直线能将凸包正好卡住。而边通常是按照向某一方向旋转的顺序来枚举，所以整个过程就是在边「旋转」，边「卡壳」。\n \n 其英文名「rotating calipers」的直译应为「旋转卡尺」，其中「calipers」的意思是「卡尺」。第一次提出该术语的论文[^ref1]原意为：使用一个可动态调整的「卡尺」夹住凸包后，绕凸包「旋转」该「卡尺」。\n\n## 求凸包直径\n\n???+ note \" 例题 1 :[Luogu P1452 Beauty Contest G](https://www.luogu.com.cn/problem/P1452)\"\n 给定平面?? $n$ 个点，求所有点对之间的最长距离。（$2\\leq n \\leq 50000,|x|,|y| \\leq 10^4$）\n\n### 过程\n\n首先使用任何一种凸包算法求出给定所有点的凸包，有着最长距离的点对一定在凸包上。而由于凸包的形状，我们发现，逆时针地遍历凸包上的边，对于每条边都找到离这条边最远的点，那么这时随着边的转动，对应的最远点也在逆时针旋转，不会有反向的情况，这意味着我们可以在逆时针枚举凸包上的边时，记录并维护一个当前最远点，并不断计算、更新答案。\n\n求出凸包后的数组自然地是按照逆时针旋转的顺序排列，不过要记得提前将最左下角的 1 节点补到数组最后，这样在挨个枚举边 $(i,i+1)$ 时，才能把所有边都枚举到。\n\n![](images/rotating-calipers1.png)\n\n枚举过程中，对于每条边，都检?? $j+1$ 和边 $(i,i+1)$ 的距离是不是?? $j$ 更大，如果是就将 $j$ 加一，否则说?? $j$ 是此边的最优点。判断点到边的距离大小时可以用叉积分别算出两个三角形的面积（如图，黄、蓝两个同底三角形的面积）并直接比较。\n\n### 实现\n\n```cpp\n int sta[N], top; // 将凸包上的节点编号存在栈里，第一个和最后一个节点编号相同\n bool is[N];\n \n ll pf(ll x) { return x * x; }\n \n ll dis(int p, int q) { return pf(a[p].x - a[q].x) + pf(a[p].y - a[q].y); }\n \n ll sqr(int p, int q, int y) { return abs((a[q] - a[p]) * (a[y] - a[q])); }\n \n ll mx;\n \n void get_longest() { // 求凸包直径\n int j = 3;\n if (top < 4) {\n mx = dis(sta[1], sta[2]);\n return;\n }\n for (int i = 1; i <= top; ++i) {\n while (sqr(sta[i], sta[i + 1], sta[j]) <=\n sqr(sta[i], sta[i + 1], sta[j % top + 1]))\n j = j % top + 1;\n mx = max(mx, max(dis(sta[i + 1], sta[j]), dis(sta[i], sta[j])));\n }\n }\n```\n \n```python\n sta = [0] * N; top = 0 # 将凸包上的节点编号存在栈里，第一个和最后一个节点编号相同\n def pf(x):\n return x * x\n def dis(p, q):\n return pf(a[p].x - a[q].x) + pf(a[p].y - a[q].y)\n def sqr(p, q, y):\n return abs((a[q] - a[p]) * (a[y] - a[q]))\n def get_longest(): # 求凸包直径\n j = 3\n if top < 4:\n mx = dis(sta[1], sta[2])\n return\n for i in range(1, top + 1):\n while sqr(sta[i], sta[i + 1], sta[j]) <=\\\n sqr(sta[i], sta[i + 1], sta[j % top + 1]):\n j = j % top + 1\n mx = max(mx, max(dis(sta[i + 1], sta[j]), dis(sta[i], sta[j])))\n```\n\n## 求最小矩形覆盖\n\n[Luogu P3187 最小矩形覆盖](https://www.luogu.com.cn/problem/P3187)\n\n给定一些点的坐标，求能够覆盖所有点的最小面积的矩形。（$3\\leq n \\leq 50000$）\n\n### 过程\n\n有了上一道题做铺垫，这道题比较直观的想法仍然是使用旋转卡壳法，不过这次要求的是面积，像上一题一样只维护一个最优点就只能找到一对距离最小的平行线，我们还需要确定矩形的左右边界。所以这次我们需要维护三个点：一个在所枚举的直线对面的点、两个在不同侧面的点。对面的最优点仍然是用叉积算面积来比较，此时比较面积就是在比较这个矩形的一个边长。侧面的最优点则是用点积来比较，因为比较点积就是比较投影的长度，左右两个投影长度相加可以代表这个矩形的另一个边长。这两个边长的最优性相互独立，因此找到三个最优点的位置就能够确定以当前边所在直线为矩阵的一条边时，能覆盖所有点的矩形最小面积。\n\n![](images/rotating-calipers2.png)\n\n最后统计答案时，如果题目没有要求将四个顶点都求出来，其实有一种较为巧妙的利用叉积和点积的方式直接算出矩阵的面积。设紫色部分面积的两倍为 $S$，最后的面积就是\n\n$$\nS\\times (|\\overrightarrow{AD}\\cdot \\overrightarrow{AB}|+|\\overrightarrow{BC}\\cdot \\overrightarrow{BA}|-|\\overrightarrow{AB}\\cdot \\overrightarrow{BA}|)/|\\overrightarrow{AB}\\cdot \\overrightarrow{BA}|\n$$\n\n### 实现\n\n必要的求凸包过程略去，这里贴出本题核心代码：\n\n```cpp\n void get_biggest() {\n int j = 3, l = 2, r = 2;\n double t1, t2, t3, ans = 2e10;\n for (int i = 1; i <= top; ++i) {\n while (sqr(sta[i], sta[i + 1], sta[j]) <=\n sqr(sta[i], sta[i + 1], sta[j % top + 1]))\n j = j % top + 1;\n while (dot(sta[i + 1], sta[r % top + 1], sta[i]) >=\n dot(sta[i + 1], sta[r], sta[i]))\n r = r % top + 1;\n if (i == 1) l = r;\n while (dot(sta[i + 1], sta[l % top + 1], sta[i]) <=\n dot(sta[i + 1], sta[l], sta[i]))\n l = l % top + 1;\n t1 = sqr(sta[i], sta[i + 1], sta[j]);\n t2 = dot(sta[i + 1], sta[r], sta[i]) + dot(sta[i + 1], sta[l], sta[i]);\n t3 = dot(sta[i + 1], sta[i + 1], sta[i]);\n ans = min(ans, t1 * t2 / t3);\n }\n }\n```\n \n```python\n def get_biggest():\n j = 3; l = 2; r = 2\n ans = 2e10\n for i in range(1, top + 1):\n while sqr(sta[i], sta[i + 1], sta[j]) <=\\\n sqr(sta[i], sta[i + 1], sta[j % top + 1]):\n j = j % top + 1\n while dot(sta[i + 1], sta[r % top + 1], sta[i]) >=\\\n dot(sta[i + 1], sta[r], sta[i]):\n r = r % top + 1\n if i == 1:\n l = r\n while dot(sta[i + 1], sta[l % top + 1], sta[i]) <=\\\n dot(sta[i + 1], sta[l], sta[i]):\n l = l % top + 1\n t1 = sqr(sta[i], sta[i + 1], sta[j])\n t2 = dot(sta[i + 1], sta[r], sta[i]) + dot(sta[i + 1], sta[l], sta[i])\n t3 = dot(sta[i + 1], sta[i + 1], sta[i])\n ans = min(ans, t1 * t2 / t3)\n```\n\n## 练习\n\n- [POJ 3608. Bridge Across Islands](http://poj.org/problem?id=3608)\n- [2011 ACM-ICPC World Finals, Problem K. Trash Removal](https://codeforces.com/gym/101175)\n- [ICPC WF Moscow Invitational Contest - Online Mirror, Problem F. Framing Pictures](https://codeforces.com/contest/1578/problem/F)\n\n## 参考资料与注释\n\n[^ref1]: Toussaint, Godfried T. (1983). \"Solving geometric problems with the rotating calipers\". Proc. MELECON \'83, Athens. CiteSeerX 10.1.1.155.5671\n\n- \n\n- \n\n- Shamos, Michael (1978). \"Computational Geometry\" (PDF). Yale University. pp. 76??81.\n') document.getElementById('render_1112').innerHTML = htmlText console.log(htmlText) htmlText = marked.parse('## 引入\n\n扫描线一般运用在图形上面，它和它的字面意思十分相似，就是一条线在整个图上扫来扫去，它一般被用来解决图形面积，周长，以及二维数点等问题。\n\n## Atlantis 问题\n\n### 题意\n\n在二维坐标系上，给出多个矩形的左下以及右上坐标，求出所有矩形构成的图形的面积。\n\n### 解法\n\n根据图片可知总面积可以直接暴力即可求出面积，如果数据大了怎么办？这时就需要讲?? **扫描??** 算法。\n\n### 过程\n\n现在假设我们有一根线，从下往上开始扫描：\n\n![](./images/scanning.svg)\n\n- 如图所示，我们可以把整个矩形分成如图各个颜色不同的小矩形，那么这个小矩形的高就是我们扫过的距离，那么剩下了一个变量，那就是矩形的长一直在变化。\n- 我们的线段树就是为了维护矩形的长，我们给每一个矩形的上下边进行标记，下面的边标记?? 1，上面的边标记为 -1，每遇到一个矩形时，我们知道了标记?? 1 的边，我们就加进来这一条矩形的长，等到扫描?? -1 时，证明这一条边需要删除，就删去，利用 1 ?? -1 可以轻松的到这种状态。\n- 还要注意这里的线段树指的并不是线段的一个端点，而指的是一个区间，所以我们要计算的是 $r+1$ ?? $r-1$。\n- 需?? [离散化](../misc/discrete.md)。\n\n### 实现\n\n```cpp\n #include \n #include \n #include \n #define maxn 300\n using namespace std;\n \n int lazy[maxn << 3]; // 标记了这条线段出现的次数\n double s[maxn << 3];\n \n struct node1 {\n double l, r;\n double sum;\n } cl[maxn << 3]; // 线段树\n \n struct node2 {\n double x, y1, y2;\n int flag;\n } p[maxn << 3]; // 坐标\n \n // 定义sort比较\n bool cmp(node2 a, node2 b) { return a.x < b.x; }\n \n // 上传\n void pushup(int rt) {\n if (lazy[rt] > 0)\n cl[rt].sum = cl[rt].r - cl[rt].l;\n else\n cl[rt].sum = cl[rt * 2].sum + cl[rt * 2 + 1].sum;\n }\n \n // 建树\n void build(int rt, int l, int r) {\n if (r - l > 1) {\n cl[rt].l = s[l];\n cl[rt].r = s[r];\n build(rt * 2, l, (l + r) / 2);\n build(rt * 2 + 1, (l + r) / 2, r);\n pushup(rt);\n } else {\n cl[rt].l = s[l];\n cl[rt].r = s[r];\n cl[rt].sum = 0;\n }\n return;\n }\n \n // 更新\n void update(int rt, double y1, double y2, int flag) {\n if (cl[rt].l == y1 && cl[rt].r == y2) {\n lazy[rt] += flag;\n pushup(rt);\n return;\n } else {\n if (cl[rt * 2].r > y1) update(rt * 2, y1, min(cl[rt * 2].r, y2), flag);\n if (cl[rt * 2 + 1].l < y2)\n update(rt * 2 + 1, max(cl[rt * 2 + 1].l, y1), y2, flag);\n pushup(rt);\n }\n }\n \n int main() {\n int temp = 1, n;\n double x1, y1, x2, y2, ans;\n while (scanf(\"%d\", &n) && n) {\n ans = 0;\n for (int i = 0; i < n; i++) {\n scanf(\"%lf %lf %lf %lf\", &x1, &y1, &x2, &y2);\n p[i].x = x1;\n p[i].y1 = y1;\n p[i].y2 = y2;\n p[i].flag = 1;\n p[i + n].x = x2;\n p[i + n].y1 = y1;\n p[i + n].y2 = y2;\n p[i + n].flag = -1;\n s[i + 1] = y1;\n s[i + n + 1] = y2;\n }\n sort(s + 1, s + (2 * n + 1)); // 离散化\n sort(p, p + 2 * n, cmp); // 把矩形的边的横坐标从小到大排序\n build(1, 1, 2 * n); // 建树\n memset(lazy, 0, sizeof(lazy));\n update(1, p[0].y1, p[0].y2, p[0].flag);\n for (int i = 1; i < 2 * n; i++) {\n ans += (p[i].x - p[i - 1].x) * cl[1].sum;\n update(1, p[i].y1, p[i].y2, p[i].flag);\n }\n printf(\"Test case #%d\\nTotal explored area: %.2lf\\n\\n\", temp++, ans);\n }\n return 0;\n }\n```\n\n## 练习\n\n- [「POJ1151」Atlantis](http://poj.org/problem?id=1151)\n\n- [「POJ1177」Picture](http://poj.org/problem?id=1177)\n\n- [「POJ3832」Posters](http://poj.org/problem?id=3832)\n\n- [洛谷 P1856\\[IOI1998\\]\\[USACO5.5\\] 矩形周长 Picture](https://www.luogu.com.cn/problem/P1856)\n\n## B 维正交范围\n\nB 维正交范围指在一?? B 维直角坐标系下，?? $i$ 维坐标在一个整数范?? $[l_i,r_i]$ 间，内部的点集。\n\n一般来说，一维正交范围简称区间，二维正交范围简称矩形，三维正交范围简称立方体（我们常说的二维数点就是二维正交范围）。\n\n对于一个静态的二维问题，我们可以使用扫描线扫一维，数据结构维护另一维。\n在扫描线从左到右扫的过程中，会在数据结构维护的那一维上产生一些修改与查询。\n如果查询的信息可差分的话直接使用差分，否则需要使用分治。差分一般用树状数组和线段树维护，但因为树状数组好写而且常数小，所以大部分人会选择用树状数组来维护。分治一般是 CDQ 分治（但是这里不涉及分治）。\n\n另一种比较容易理解的看待问题的角度是站在序列角度，而不站在二维平面角度。如果我们这样看待问题，则扫描线实际上是枚举了右端点 $r=1\\cdots n$，维护一个数据结构，支持查询对于当前?? $r$，给定一个?? $l$??$l$ ?? $r$ 的答案是什么。即扫描线扫询问右端点，数据结构维护所有左端点的答案，或者说遍历一维，数据结果维护另一维。\n\n复杂度一般为 $\\mathcal O((n+m)\\log n)$。\n\n### 二维数点\n\n给一个长?? $n$ 的序列，?? $m$ 次查询，每次查区?? $[l,r]$ 中值在 $[x,y]$ 内的元素个数。\n\n这个问题就叫做二维数点。我们可以发现等价于我们要查询一个二维平面上矩形内的点的数量和。这里讲一下这个问题最简单的处理方法，扫描线 + 树状数组。\n\n很显然，这个问题是一个静态的二维问题，我们通过扫描线可以将静态的二维问题转换为动态的一维问题。维护动态的一维问题就使用数据结构维护序列，这里可以使用树状数组。\n\n先将所有的询问离散化，用树状数组维护权值，对于每次询问?? $l$ ?? $r$，我们在枚举?? $l-1$ 时统计当前位于区?? $[x,y]$ 内的数的数量 $a$，继续向后枚举，枚举?? $r$ 时统计当前位于区?? $[x,y]$ 内的数的数量 $b$??$b-a$ 即为该次询问的答案。\n\n可以?? [洛谷 P2163\\[SHOI2007\\] 园丁的烦恼](https://www.luogu.com.cn/problem/P2163) 这道题进行练习。\n\n### 例题\n\n???+ note \"[洛谷 P1908 逆序对](https://www.luogu.com.cn/problem/P1908)\"\n 没错，逆序对也可以用扫描线的思维来做。考虑将求逆序对的个数转化为从后向前枚举每个位?? $i$，求在区?? $[i+1,n]$ 中，大小在区?? $[0,a_i]$ 中的点的个数。题目中数据范围?? $10^9$，很显然要先进行离散化，我们可以考虑从后向前遍历数组，每次遍历到一个数时更新数组数组（线段树），之后统计当前一共有多少个数小于当前枚举的数，因为我们是从后向前遍历的，所以比当前值小的数的个数就是他的逆序对的个数，可以用树状数组或线段树进行单点修改和区间查诀??\n \n```cpp\n --8<-- \"docs/geometry/code/scanning/scanning_1.cpp\"\n```\n\n简要题意：给定一个长?? $n$ 的序列，$m$ 次查询区间中有多少不同的数。\n \n这类问题我们可以考虑推导性质，之后使用扫描线枚举所有右端点，数据结构维护每个左端点的答案的方法来实现，我们也可以将问题转换到二维平面上，变为一个矩形查询信息的问题。\n \n在这道题中，对于每个位置 $i$，考虑预处理出 $i$ 左边?? $i$ 最近的 $j$ 满足 $a_i=a_j$，用一个数组记录，?? $pre_i=j$。\n \n然后查询区间中的不同数，我们可以只把每个数在区间中最后一次出现时统计进去。\n \n若这个数在当前区间中是第一次出现，那么这个数肯定满?? $pre_i < l$。如果不是第一次出现，那么 $l \\le pre_i$。这样问题就转变成了求区?? $[l,r]$ 中，满足 $pre_i < l$ ?? $i$ 的个数。\n \n 我们可以考虑差分，将区间 $[l,r]$ 差分为前缀 $[1,r]$ 减去前缀 $[1,l-1]$。考虑将询问离线处理，假设有一个询问是对于区间 $[l,r]$ 的，我们?? $l-1$ 位置上和 $r$ 位置上分别记录一下，答案为在 $r$ 处记录的 $pre_i < l$ 的个数减去在 $l-1$ 处记录的 $pre_i < l$ ?? $i$ 的个数。\n \n每次查询可以用值域线段树或值域树状数组来维护，注意一个位置上可能有多个询问，但总共的查询次数是 $m$ 次。总时间复杂度 $\\mathcal O((n+m)\\log n)$。\n \n```cpp\n --8<-- \"docs/geometry/code/scanning/scanning_2.cpp\"\n```\n\n### 例题\n\n- [洛谷 P8593「KDOI-02」一个弹的投](https://www.luogu.com.cn/problem/P8593) 逆序对的应用。\n\n- [AcWing 4709. 三元组](https://www.acwing.com/problem/content/4712/) 上题的弱化版，同样为逆序对的应用。\n\n- [洛谷 P8773\\[蓝桥?? 2022 ?? A\\] 选数异或](https://www.luogu.com.cn/problem/P8773) HH 的项链魔改版。\n\n- [洛谷 P8844\\[传智?? #4 初赛\\] 小卡与落叶](https://www.luogu.com.cn/problem/P8844) 树上问题转序列问题然后进行二维数点。\n\n总而言之，二维数点的主要思路就是数据结构维护一维，然后枚举另一维。\n\n## 参考资料\n\n- \n\n- \n\n- \n\n- \n') document.getElementById('render_1113').innerHTML = htmlText console.log(htmlText) htmlText = marked.parse('author: xehoth\n\n在几何中，三角剖分是指将平面对象细分为三角形，并且通过扩展将高维几何对象细分为单纯彀??\n对于一个给定的点集，有很多种三角剖分，如：\n\n![三种三角剖分](./images/triangulation-0.svg)\n\nOI 中的三角剖分主要指二维几何中的完美三角剖分（二维 Delaunay 三角剖分，简?? DT）。\n\n## Delaunay 三角剖分\n\n### 定义\n\n在数学和计算几何中，对于给定的平面中的离散点?? $P$，其 Delaunay 三角剖分 DT($P$) 满足：\n\n1. 空圆性：DT($P$) ?? **唯一** 的（任意四点不能共圆），?? DT($P$) 中，**任意** 三角形的外接圆范围内不会有其它点存在。\n2. 最大化最小角：在点集 $P$ 可能形成的三角剖分中，DT($P$) 所形成的三角形的最小角最大。从这个意义上讲，DT($P$) ?? **最接近于规则化** 的三角剖分。具体的说是在两个相邻的三角形构成凸四边形的对角线，在相互交换后，两个内角的最小角不再增大。\n\n![一个显示了外接圆的 Delaunay 三角剖分](./images/triangulation-1.png)\n\n### 性质\n\n1. 最接近：以最接近的三点形成三角形，且各线段（三角形的边）皆不相交。\n2. 唯一性：不论从区域何处开始构建，最终都将得到一致的结果（点集中任意四点不能共圆）。\n3. 最优性：任意两个相邻三角形构成的凸四边形的对角线如果可以互换的话，那么两个三角形六个内角中最小角度不会变化。\n4. 最规则：如果将三角剖分中的每个三角形的最小角进行升序排列，则 Delaunay 三角剖分的排列得到的数值最大。\n5. 区域性：新增、删除、移动某一个顶点只会影响邻近的三角彀??\n6. 具有凸边形的外壳：三角剖分最外层的边界形成一个凸多边形的外壳。\n\n## 构?? DT 的分治算法\n\nDT 有很多种构造算法，?? $O(n \\log n)$ 的构造算法中，分治算法是最易于理解和实现的。\n\n分治构?? DT 的第一步是将给定点集按?? $x$ 坐标 **升序** 排列，如下图是排好序的大小为 $10$ 的点集。\n\n![排好序的大小?? 10 的点集](./images/triangulation-2.svg)\n\n一旦点集有序，我们就可以不断地将其分成两个部分（分治），直到子点集大小不超?? $3$。然后这些子点集可以立刻剖分为一个三角形或线段。\n\n![分治为包?? 2 ?? 3 个点的点集](./images/triangulation-3.svg)\n\n然后在分治回溯的过程中，已经剖分好的左右子点集可以依次合并。合并后的剖分包?? LL-edge（左侧子点集的边）。RR-edge（右侧子点集的边），LR-edge（连接左右剖分产生的新的边），如?? LL-edge（灰色），RR-edge（红色），LR-edge（蓝色）。对于合并后的剖分，为了维持 DT 性质，我?? **可能** 需要删除部?? LL-edge ?? RR-edge，但我们在合并时 **不会** 增加 LL-edge ?? RR-edge。\n\n![edge](./images/triangulation-4.svg)\n\n合并左右两个剖分的第一步是插入 base LR-edge，base LR-edge ?? **最底部** 的不?? **任何** LL-edge ?? RR-edge 相交?? LR-edge。\n\n![合并左右剖分](./images/triangulation-5.svg)\n\n然后，我们需要确定下一?? **紧接??** base LR-edge 之上?? LR-edge。比如对于右侧点集，下一?? LR-edge 的可能端点（右端点）为与 base LR-edge 右端点相连的 RR-edge 的另一端点??$6, 7, 9$ 号点），左端点即?? $2$ 号点。\n\n![下一?? LR-edge](./images/triangulation-6.svg)\n\n对于可能的端点，我们需要按以下两个标准检验：\n\n1. 其对?? RR-edge ?? base LR-edge 的夹角小?? $180$ 度。\n2. base LR-edge 两端点和这个可能点三点构成的圆内不包含任何其?? **可能??**。\n\n![检验可能点](./images/triangulation-7.svg)\n\n如上图，$6$ 号可能点所对应的绿色圆包含?? $9$ 号可能点，?? $7$ 号可能点对应的紫色圆则不包含任何其它可能点，?? $7$ 号点为下一?? LR-edge 的右端点。\n\n对于左侧点集，我们做镜像处理即可。\n\n![检验左侧可能点](./images/triangulation-8.svg)\n\n当左右点集都不再含有符合标准的可能点时，合并即完成。当一个可能点符合标准，一?? LR-edge 就需要被添加，对于与需要添加的 LR-edge 相交?? LL-edge ?? RR-edge，将其删除。\n\n当左右点集均存在可能点时，判断左边点所对应圆是否包含右边点，若包含则不符合；对于右边点也是同样的判断。一般只有一个可能点符合标准（除非四点共圆）。\n\n![下一?? LR-edge](./images/triangulation-9.svg)\n\n当这?? LR-edge 添加好后，将其作?? base LR-edge 重复以上步骤，继续添加下一条，直到合并完成。\n\n![合并](./images/triangulation-10.svg)\n\n## 代码\n\n```cpp\n #include \n #include \n #include \n #include \n #include \n #include \n \n const double EPS = 1e-8;\n const int MAXV = 10000;\n \n struct Point {\n double x, y;\n int id;\n \n Point(double a = 0, double b = 0, int c = -1) : x(a), y(b), id(c) {}\n \n bool operator<(const Point &a) const {\n return x < a.x || (fabs(x - a.x) < EPS && y < a.y);\n }\n \n bool operator==(const Point &a) const {\n return fabs(x - a.x) < EPS && fabs(y - a.y) < EPS;\n }\n \n double dist2(const Point &b) {\n return (x - b.x) * (x - b.x) + (y - b.y) * (y - b.y);\n }\n };\n \n struct Point3D {\n double x, y, z;\n \n Point3D(double a = 0, double b = 0, double c = 0) : x(a), y(b), z(c) {}\n \n Point3D(const Point &p) { x = p.x, y = p.y, z = p.x * p.x + p.y * p.y; }\n \n Point3D operator-(const Point3D &a) const {\n return Point3D(x - a.x, y - a.y, z - a.z);\n }\n \n double dot(const Point3D &a) { return x * a.x + y * a.y + z * a.z; }\n };\n \n struct Edge {\n int id;\n std::list::iterator c;\n \n Edge(int id = 0) { this->id = id; }\n };\n \n int cmp(double v) { return fabs(v) > EPS ? (v > 0 ? 1 : -1) : 0; }\n \n double cross(const Point &o, const Point &a, const Point &b) {\n return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x);\n }\n \n Point3D cross(const Point3D &a, const Point3D &b) {\n return Point3D(a.y * b.z - a.z * b.y, -a.x * b.z + a.z * b.x,\n a.x * b.y - a.y * b.x);\n }\n \n int inCircle(const Point &a, Point b, Point c, const Point &p) {\n if (cross(a, b, c) < 0) std::swap(b, c);\n Point3D a3(a), b3(b), c3(c), p3(p);\n b3 = b3 - a3, c3 = c3 - a3, p3 = p3 - a3;\n Point3D f = cross(b3, c3);\n return cmp(p3.dot(f)); // check same direction, in: < 0, on: = 0, out: > 0\n }\n \n int intersection(const Point &a, const Point &b, const Point &c,\n const Point &d) { // seg(a, b) and seg(c, d)\n return cmp(cross(a, c, b)) * cmp(cross(a, b, d)) > 0 &&\n cmp(cross(c, a, d)) * cmp(cross(c, d, b)) > 0;\n }\n \n class Delaunay {\n public:\n std::list head[MAXV]; // graph\n Point p[MAXV];\n int n, rename[MAXV];\n \n void init(int n, Point p[]) {\n memcpy(this->p, p, sizeof(Point) * n);\n std::sort(this->p, this->p + n);\n for (int i = 0; i < n; i++) rename[p[i].id] = i;\n this->n = n;\n divide(0, n - 1);\n }\n \n void addEdge(int u, int v) {\n head[u].push_front(Edge(v));\n head[v].push_front(Edge(u));\n head[u].begin()->c = head[v].begin();\n head[v].begin()->c = head[u].begin();\n }\n \n void divide(int l, int r) {\n if (r - l <= 2) { // #point <= 3\n for (int i = l; i <= r; i++)\n for (int j = i + 1; j <= r; j++) addEdge(i, j);\n return;\n }\n int mid = (l + r) / 2;\n divide(l, mid);\n divide(mid + 1, r);\n \n std::list::iterator it;\n int nowl = l, nowr = r;\n \n for (int update = 1; update;) {\n // find left and right convex, lower common tangent\n update = 0;\n Point ptL = p[nowl], ptR = p[nowr];\n for (it = head[nowl].begin(); it != head[nowl].end(); it++) {\n Point t = p[it->id];\n double v = cross(ptR, ptL, t);\n if (cmp(v) > 0 || (cmp(v) == 0 && ptR.dist2(t) < ptR.dist2(ptL))) {\n nowl = it->id, update = 1;\n break;\n }\n }\n if (update) continue;\n for (it = head[nowr].begin(); it != head[nowr].end(); it++) {\n Point t = p[it->id];\n double v = cross(ptL, ptR, t);\n if (cmp(v) < 0 || (cmp(v) == 0 && ptL.dist2(t) < ptL.dist2(ptR))) {\n nowr = it->id, update = 1;\n break;\n }\n }\n }\n \n addEdge(nowl, nowr); // add tangent\n \n for (int update = 1; true;) {\n update = 0;\n Point ptL = p[nowl], ptR = p[nowr];\n int ch = -1, side = 0;\n for (it = head[nowl].begin(); it != head[nowl].end(); it++) {\n if (cmp(cross(ptL, ptR, p[it->id])) > 0 &&\n (ch == -1 || inCircle(ptL, ptR, p[ch], p[it->id]) < 0)) {\n ch = it->id, side = -1;\n }\n }\n for (it = head[nowr].begin(); it != head[nowr].end(); it++) {\n if (cmp(cross(ptR, p[it->id], ptL)) > 0 &&\n (ch == -1 || inCircle(ptL, ptR, p[ch], p[it->id]) < 0)) {\n ch = it->id, side = 1;\n }\n }\n if (ch == -1) break; // upper common tangent\n if (side == -1) {\n for (it = head[nowl].begin(); it != head[nowl].end();) {\n if (intersection(ptL, p[it->id], ptR, p[ch])) {\n head[it->id].erase(it->c);\n head[nowl].erase(it++);\n } else {\n it++;\n }\n }\n nowl = ch;\n addEdge(nowl, nowr);\n } else {\n for (it = head[nowr].begin(); it != head[nowr].end();) {\n if (intersection(ptR, p[it->id], ptL, p[ch])) {\n head[it->id].erase(it->c);\n head[nowr].erase(it++);\n } else {\n it++;\n }\n }\n nowr = ch;\n addEdge(nowl, nowr);\n }\n }\n }\n \n std::vector > getEdge() {\n std::vector > ret;\n ret.reserve(n);\n std::list::iterator it;\n for (int i = 0; i < n; i++) {\n for (it = head[i].begin(); it != head[i].end(); it++) {\n if (it->id < i) continue;\n ret.push_back(std::make_pair(p[i].id, p[it->id].id));\n }\n }\n return ret;\n }\n };\n```\n\n## Voronoi 图\n\nVoronoi 图由一组由连接两邻点直线的垂直平分线组成的连续多边形组成，根据 $n$ 个在平面上不重合种子点，把平面分?? $n$ 个区域，使得每个区域内的点到它所在区域的种子点的距离比到其它区域种子点的距离近。\n\nVoronoi 图是 Delaunay 三角剖分的对偶图，可以使用构?? Delaunay 三角剖分的分治算法求出三角网，再使用最左转线算法求出其对偶图实现在 $O(n \\log n)$ 的时间复杂度下构?? Voronoi 图。\n\n## 题目\n\n[SGU 383 Caravans](https://codeforces.com/problemsets/acmsguru/problem/99999/383) 三角剖分 + 倍增\n\n[ContestHunter. 无尽的毁灭](http://noi-test.zzstep.com/contest/Beta%20Round%20%EF%BC%832%20%28%E6%96%B0%E7%96%86%E7%9C%81%E9%98%9F%E4%BA%92%E6%B5%8BWeek1-Day2%29/%E6%97%A0%E5%B0%BD%E7%9A%84%E6%AF%81%E7%81%AD) 三角剖分求对偶图?? Voronoi 图\n\n[Codeforces Gym 103485M. Constellation collection](https://codeforces.com/gym/103485/problem/M) 三角剖分之后建图进行 Floodfill\n\n## 参考资料与拓展阅读\n\n1. [Wikipedia - Triangulation (geometry)](https://en.wikipedia.org/wiki/Triangulation_%28geometry%29)\n2. [Wikipedia - Delaunay triangulation](https://en.wikipedia.org/wiki/Delaunay_triangulation)\n3. Samuel Peterson -[Computing Constrained Delaunay Triangulations in 2-D (1997-98)](http://www.geom.uiuc.edu/~samuelp/del_project.html)\n') document.getElementById('render_1114').innerHTML = htmlText setTimeout( ()=>{ console.log("delay render mathjax",MathJax) MathJax.Hub.Config({ tex2jax: { inlineMath: [['$', '$'], ['\\(', '\\)']] } }); // entry-content是文章页的内容div的class console.log(600) var math = document.getElementById('render_600')[0]; MathJax.Hub.Queue(["Typeset", MathJax.Hub, math]); console.log(112) var math = document.getElementById('render_112')[0]; MathJax.Hub.Queue(["Typeset", MathJax.Hub, math]); console.log(120) var math = document.getElementById('render_120')[0]; MathJax.Hub.Queue(["Typeset", MathJax.Hub, math]); console.log(128) var math = document.getElementById('render_128')[0]; MathJax.Hub.Queue(["Typeset", MathJax.Hub, math]); console.log(129) var math = document.getElementById('render_129')[0]; MathJax.Hub.Queue(["Typeset", MathJax.Hub, math]); console.log(131) var math = document.getElementById('render_131')[0]; MathJax.Hub.Queue(["Typeset", MathJax.Hub, math]); console.log(133) var math = document.getElementById('render_133')[0]; MathJax.Hub.Queue(["Typeset", MathJax.Hub, math]); console.log(145) var math = document.getElementById('render_145')[0]; MathJax.Hub.Queue(["Typeset", MathJax.Hub, math]); console.log(156) var math = document.getElementById('render_156')[0]; MathJax.Hub.Queue(["Typeset", MathJax.Hub, math]); console.log(169) var math = document.getElementById('render_169')[0]; MathJax.Hub.Queue(["Typeset", MathJax.Hub, math]); console.log(176) var math = document.getElementById('render_176')[0]; MathJax.Hub.Queue(["Typeset", MathJax.Hub, math]); console.log(751) var math = document.getElementById('render_751')[0]; MathJax.Hub.Queue(["Typeset", MathJax.Hub, math]); console.log(804) var math = document.getElementById('render_804')[0]; MathJax.Hub.Queue(["Typeset", MathJax.Hub, math]); console.log(805) var math = document.getElementById('render_805')[0]; MathJax.Hub.Queue(["Typeset", MathJax.Hub, math]); console.log(812) var math = document.getElementById('render_812')[0]; MathJax.Hub.Queue(["Typeset", MathJax.Hub, math]); console.log(817) var math = document.getElementById('render_817')[0]; MathJax.Hub.Queue(["Typeset", MathJax.Hub, math]); console.log(1102) var math = document.getElementById('render_1102')[0]; MathJax.Hub.Queue(["Typeset", MathJax.Hub, math]); console.log(1103) var math = document.getElementById('render_1103')[0]; MathJax.Hub.Queue(["Typeset", MathJax.Hub, math]); console.log(1104) var math = document.getElementById('render_1104')[0]; MathJax.Hub.Queue(["Typeset", MathJax.Hub, math]); console.log(1105) var math = document.getElementById('render_1105')[0]; MathJax.Hub.Queue(["Typeset", MathJax.Hub, math]); console.log(1106) var math = document.getElementById('render_1106')[0]; MathJax.Hub.Queue(["Typeset", MathJax.Hub, math]); console.log(1109) var math = document.getElementById('render_1109')[0]; MathJax.Hub.Queue(["Typeset", MathJax.Hub, math]); console.log(1110) var math = document.getElementById('render_1110')[0]; MathJax.Hub.Queue(["Typeset", MathJax.Hub, math]); console.log(1111) var math = document.getElementById('render_1111')[0]; MathJax.Hub.Queue(["Typeset", MathJax.Hub, math]); console.log(1112) var math = document.getElementById('render_1112')[0]; MathJax.Hub.Queue(["Typeset", MathJax.Hub, math]); console.log(1113) var math = document.getElementById('render_1113')[0]; MathJax.Hub.Queue(["Typeset", MathJax.Hub, math]); console.log(1114) var math = document.getElementById('render_1114')[0]; MathJax.Hub.Queue(["Typeset", MathJax.Hub, math]); },2000 ) });
计算机图形学 历史版本:
上次修改时间:
opengl 可编程管线shader介绍 历史版本:
上次修改时间: 2021-01-21 00:54:49
齐次变换绕不通过原点的直线旋转 历史版本:
上次修改时间: 2021-01-21 00:54:49
opengl VBO使用 历史版本:
上次修改时间: 2021-01-21 00:54:49
opengl渲染管线 历史版本:
上次修改时间: 2021-01-29 01:36:58
计算机图形学的基础变换 历史版本:
上次修改时间: 2021-01-28 23:52:25
基于glut opengl 常见变换的设置方法 历史版本:
上次修改时间: 2021-01-21 00:54:49
常见图形处理方法及应用 历史版本:
上次修改时间: 2021-01-21 00:54:49
关于人脸检测的实现 历史版本:
上次修改时间: 2021-01-21 00:54:49
opengl可编程着色器-顶点着色器 历史版本:
上次修改时间: 2021-01-21 00:54:49
可编程管线中opengl 顶点和纹理的使用 历史版本:
上次修改时间: 2021-01-21 00:54:49
深度测试 历史版本:
上次修改时间: 2023-01-13 11:04:17
opengl 历史版本:
上次修改时间:
opengl es 历史版本:
上次修改时间: 2023-03-29 00:09:11
VTK工具库 历史版本:
上次修改时间: 2023-04-13 00:23:28
webgl和tree.js 历史版本:
上次修改时间: 2023-04-22 22:04:59
\n\n\n\n\n\n\n```\n\n\n效果\n\n\n\n\n -->
平面几何 历史版本:
上次修改时间:
三维几何 历史版本:
上次修改时间:
二维凸包 历史版本:
上次修改时间:
欧氏距离 历史版本:
上次修改时间:
半平?? 历史版本:
上次修改时间:
欧几里得距离 历史版本:
上次修改时间:
Pick 定理 历史版本:
上次修改时间:
随机增量算法 历史版本:
上次修改时间:
旋转卡壳 历史版本:
上次修改时间:
扫描?? 历史版本:
上次修改时间:
Delaunay 三角剖分 历史版本:
上次修改时间:
0条评�?
全部评论

关于博主

an actually real engineer

通信工程专业毕业,7年开发经验

技术栈:

精通c/c++

精通golang

熟悉常见的脚本,js,lua,python,php

熟悉电路基础,嵌入式,单片机

耕耘领域:

服务端开发

嵌入式开发

git

>

gin接口代码CURD生成工具

sql ddl to struct and markdown,将sql表自动化生成代码内对应的结构体和markdown表格格式,节省宝贵的时间。

输入ddl:
输出代码:

qt .ui文件转css文件

duilib xml 自动生成绑定控件代码

协议调试器

基于lua虚拟机的的协议调试器软件 支持的协议有:

串口

tcp客户端/服务端

udp 组播/udp节点

tcp websocket 客户端/服务端

软件界面

使用例子: 通过脚本来获得接收到的数据并写入文件和展示在界面上

下载地址和源码

duilib版本源码 qt qml版本源码 二进制包

webrtc easy demo

webrtc c++ native 库 demo 实现功能:

基于QT

webrtc摄像头/桌面捕获功能

opengl渲染/多播放窗格管理

janus meeting room

下载地址和源码

源码 二进制包

wifi,蓝牙 - 无线开关

实现功能:

通过wifi/蓝牙实现远程开关电器或者其他电子设备

电路原理图:

实物图:

深度学习验证工具

vtk+pcl 点云编辑工具

实现功能:

1. 点云文件加载显示(.pcd obj stl)

2. 点云重建

3. 点云三角化

4. 点云缩放

下载地址:

源码 二进制包

虚拟示波器

硬件实物图:

实现原理

基本性能

采集频率: 取决于外部adc模块和ebaz4205矿板的以太网接口速率,最高可以达到100M/8 约为12.5MPS

上位机实现功能: 采集,显示波形,存储wave文件。

参数可运行时配置

上位机:

显示缓冲区大小可调

刷新率可调节

触发显示刷新可调节

进程守护工具

基本功能:

1. 守护进程,被守护程序崩溃后自动重启。

2. 进程输出获取,显示在编辑框中。

二进制包

openblt 烧录工具

基本功能:

1. 加载openblt 文件,下载到具有openblt bootloader 运行的单片机中。

二进制包

opencv 功能验证工具(开源项目二次开发)

基本功能:

1. 插件化图像处理流程,支持自定义图像处理流程。 2. 完善的日志和权限管理

二进制包

又一个modbus调试工具

最近混迹物联网企业,发现目前缺少一个简易可用的modbus调试工具,本软件旨在为开发者提供一个简单modbus测试工具。
主打一个代码简单易修改。
特点:

1. 基于QT5

2. 基于libmodbus

3. 三方库完全跨平台,linux/windows。

二进制包

屏幕录制工具

1. 基于QT5

2. 基于ffmpeg

3. 支持自定义录屏

源代码

开源plutosdr 板卡

1. 完全开源

2. 提高固件定制服务

3. 硬件售价450 手焊产量有线

测试数据

内部DDS回环测试

接收测试

外部发送500MHZ FM波形

硬件原理图

matlab测试

2TRX版本

大部分plutosdr应用场景都是讲plutosdr板卡作为射频收发器来使用。
实际上plutosdr板卡本身运行linux 操作系统。是具有一定脱机运算的能力。 对于一些微型频谱检测,简单射频信号收发等应用完全可以将应用层直接实现在板卡上
相较于通过网卡或者USB口传输具有更稳定,带宽更高等优点。
本开源板卡由于了SD卡启动,较原版pluto支持了自定义启动应用的功能。
提供了应用层开发SDK(编译器，buildroot文件系统)。
通过usb连接电脑,经过RNDIS驱动可以近似为通过网卡连接
(支持固件的开发定制)。

二次开发例子

``` all:
arm-linux-gnueabihf-gcc -mfloat-abi=hard --sysroot=/root/v0.32_2trx/buildroot/output/staging -std=gnu99 -g -o pluto_stream ad9361-iiostream.c -lpthread -liio -lm -Wall -Wextra -lrt
clean:
rm pluto_stream

bsdiff算法补丁生成器

1. 官方bsdiff算法例子自带bzip压缩方式

2. 本例子没有压缩,直接生成补丁文件

3. 图形化界面基于DUILIB

二进制文件

版面分析即分析出图片内的具体文件元素,如文档标题,文档内容,文档页码等,本工具基于cnstd模型

Base64 Image