模
(|(x,y)|=sqrt{x^2 y^2})
点积
((ax,ay)*(bx,by)=ax*bx ay*by)
叉积
((ax,ay)times(bx,by)=ax*by-ay*bx)
夹角
(<vec a,vec b>)表示从(vec a)逆时针旋转到(vec b)的角度。
(cos<vec a,vec b>=frac{vec a*vec b}{|vec a||vec b|})
(sin<vec a,vec b>=frac{vec atimesvec b}{|vec a||vec b|})
极角
((x,y))的极角(varphi=<(1,0),(x,y)>=operatorname{arctan}frac yx)。
面积
(vec a)与(vec b)所成平行四边形的面积为(|vec atimesvec b|)。
旋转
((x,y))逆时针旋转(theta)得到((xcostheta-ysintheta,ycostheta xsintheta))。
线段相交
((vec{a_1},vec{a_2}),(vec{b_1},vec{b_2}))相交(Leftrightarrow)(((vec{b_1}-vec{a_1})times(vec{b_1}-vec{a_2}))((vec{b_2}-vec{a_1})times(vec{b_2}-vec{a_2}))le0wedge((vec{a_1}-vec{b_1})times(vec{a_1}-vec{b_2}))((vec{a_2}-vec{b_1})times(vec{a_2}-vec{b_2}))le0)
直线交点
先用叉积判断平行，然后利用定比分点计算。
((vec{a_1},vec{a_2}),(vec{b_1},vec{b_2}))的交点为(vec{a_1} frac{(vec{b_2}-vec{b_1})times(vec{a_2}-vec{a_1})}{(vec{b_2}-vec{b_1})times(vec{b_1}-vec{a_1})}(vec{a_2}-vec{a_1}))。
凸包
给定点集(X)，所有包含(X)的凸多边形的交称作(X)的凸包。
默认凸包有一原点为((0,0))
Graham扫描法
选取横坐标最小的点作为原点，并将其它的点按与原点连成的向量按极角排序（极角相同的按模长升序排序）。
接下来分别求出上凸包与下凸包，以下凸包为例。
我们用栈维护凸包，设当前点为(now)，栈顶和第二个点分别为(A,B)，若(A)在直线((B,now))的上方，那么将(A)弹出。
求上凸包的过程类似，将“上方”改为“下方”即可。
Mincowsky和
(X,Y)两个点集的Mincowsky和(X Y={x y|xin X,yin Y})。
可以看到(X Y)的边是由(X,Y)的边构成的。
因此我们可以把(X,Y)的边归并排序，然后为了处理三点共线的情况再用Graham扫描法求一遍凸包就好了。
判断点是否在凸包内
先判断与边界的关系，然后找到与其极角相邻的两点进行判断。
面积
以原点为中心三角剖分，然后直接叉积求即可。
多边形
判断点是否在多边形内
从该点引一射线，若与多边形相交偶数次则在凸包内。