计算几何
基础
欧几里得距离： $ \sqrt{(x1-x2)^2 + (y1-y2)^2} $
曼哈顿距离： $ \left| x1-x2 \right| + \left| y1-y2 \right| $
切比雪夫距离： $ \max(\left|x1-x2\right|,\left|y1-y2\right|) $
曼哈顿转切比雪夫： $ (x,y) $ -> $ (x+y,x-y) $
切比雪夫转曼哈顿： $ (x,y) $ -> $ (\frac{x+y}{2},\frac{x-y}{2}) $
已知顶点坐标求三角形面积
-
海伦公式
-
叉积，可以参照上一篇blog
Pick定理：这东西除了在某场远古时期CSP-J模拟赛出过外没见过一次。
令顶点均为整点的一个多边形面积为 $ S $ ，内部整点数为 $ i $ ，边上整点数为 $ j $ ，则有 $ S = i + \frac{j}{2} - 1 $
凸包：板子andrew,graham
前者，以横坐标第一关键字，纵坐标第二关键字排序。
接着分别从前向后，从后向前，求出上凸壳，下凸壳，使用单调栈+叉积可以判断
后者，从纵坐标最小的点开始，按极角排序，依次加入，同样用叉积判断
前者比较常用
-
求凸包面积：比较容易想到的是固定两个点进行三角划分计算
-
判断点在凸包内：三角划分，将总面积与凸包面积比较
合并凸包：总点集跑凸包
闵可夫斯基和合并凸包
设原来两个凸包各有 $ n,m $ 条边，则合并后的凸包有 $ n + m $ 条边
可以把把凸集按极角排序，这样可以确定边的顺序，随便钦定一个起点放边即可（oiwiki上写的类似归并的方法，可能也不用）
扫描线：并不高深，其实就是离散化（+xds），我觉得这我肯定会