From 3fa3b10609fb7a8f59d2933f6e97584bfb827afe Mon Sep 17 00:00:00 2001
From: wjy-yy <36905782+wjy-yy@users.noreply.github.com>
Date: Sun, 3 Mar 2019 20:28:18 +0800
Subject: [PATCH] =?utf8?q?=E6=B7=BB=E5=8A=A0=E4=BA=86=E5=8D=8A=E5=B9=B3?=
 =?utf8?q?=E9=9D=A2=E4=BA=A4=E7=9A=84=E6=B3=A8=E6=84=8F=E4=BA=8B=E9=A1=B9?=
MIME-Version: 1.0
Content-Type: text/plain; charset=utf8
Content-Transfer-Encoding: 8bit

---
 docs/geometry/half-plane-intersection.md | 27 +++++++++++++++++++++++++--
 1 file changed, 25 insertions(+), 2 deletions(-)

diff --git a/docs/geometry/half-plane-intersection.md b/docs/geometry/half-plane-intersection.md
index 58c83032..5ed87200 100644
--- a/docs/geometry/half-plane-intersection.md
+++ b/docs/geometry/half-plane-intersection.md
@@ -58,9 +58,9 @@ C 语言有一个库函数叫做 `atan2(double y,double x)`，可以返回 $\the
 
 还有一种可能的情况是快结束的时候，新加入的向量会从队首开始造成影响。
 
-![队首影响](./images/hpi3.PNG)
+![队首影响](./images/hpi7.PNG)
 
-仍然假设取向量左侧半平面。加入向量 $\vec e$ 之后，第一个交点 $G$ 就在 $\vec e$ 的右侧，我们把上面的判断标准逆过来看，就知道此时应该删除向量 $\vec a$，也即**队首**的向量。
+仍然假设取向量左侧半平面。加入向量 $\vec f$ 之后，第一个交点 $G$ 就在 $\vec f$ 的右侧，我们把上面的判断标准逆过来看，就知道此时应该删除向量 $\vec a$，也即**队首**的向量。
 
 最后用队首的向量排除一下队尾多余的向量。因为队首的向量会被后面的约束，而队尾的向量不会。此时它们围成了一个环，因此队首的向量就可以约束队尾的向量。
 
@@ -72,6 +72,28 @@ C 语言有一个库函数叫做 `atan2(double y,double x)`，可以返回 $\the
 
 偶尔会出现半平面交不存在或面积为 0 的情况，注意考虑边界。
 
+### 注意事项
+
+当出现一个可以把队列里的点全部弹出去的向量（即所有队列里的点都在该向量的右侧），则我们**必须**先处理队尾，再处理队首。因此在循环中，我们先枚举`--r;`的部分，再枚举`++l;`的部分，才不会错。原因如下。
+
+![](./image/hpi4.PNG)
+
+一般情况下，我们在队列 (队列顺序为 $\left\{\vec{u},\vec{v}\right\}$) 后面加一条边（向量 $\vec w$），会产生一个交点 $N$ ，缩小 $\vec{v}$ 后面的范围。
+
+![](./image/hpi5.PNG)
+
+但是毕竟每次操作都是一般的，因此可能会有把 $M$ 点“挤出去”的情况。
+
+![](./image/hpi6.PNG)
+
+如果此时出现了向量 $\vec a$ ，使得 $M$ 在 $\vec a$ 的右侧，那么 $M$ 就要出队了。此时如果从队首枚举`++l`，显然是扩大了范围。实际上 $M$ 点是由 $\vec u$ 和 $\vec v$ 共同构成的，因此需要考虑影响到现有进程的是 $\vec u$ 还是 $\vec v$。而因为我们在极角排序后，向量是逆时针顺序，所以 $\vec v$ 的影响要更大一些。
+
+就如上图，如果 $M$ 确认在 $\vec a$ 的右侧，那么此时 $\vec v$ 的影响一定不会对半平面交的答案作出任何贡献。
+
+而我们排除队首的原因是**当前向量的限制比队首向量要大**，这个条件的前提是队列里有不止两个线段（向量），不然就会出现上面的情况。
+
+所以一定要先排除队尾再排除队首。
+
 ## 代码
 
 比较部分
@@ -100,6 +122,7 @@ int l=0,r=0;
 for(int i=1;i<=n;++i)
     if((s[i]==s[i-1])==false)
     {
+        //注意要先检查队尾
         while(r-l>1&&(s[i].b-t[r])*(s[i].a-t[r])>eps)//如果上一个交点在向量右侧则弹出队尾
             --r;
         while(r-l>1&&(s[i].b-t[l+2])*(s[i].a-t[l+2])>eps)//如果第一个交点在向量右侧则弹出队首
-- 
2.11.0