其他
- $/pi$的值
1 const double pi = acos(-1.0); - 精度判断
精度三态函数1 #define eps 1e-8 2 //大于0返回1，小于返回-1，等于返回0 3 double pd(double x){ 4 if(abs(x)<=eps) return 0; 5 if(x>0) return 1; 6 return -1; 7 }
向量和点
存储
- 可以用(x,y)存储向量和点
1 struct Point 2 { 3 double x, y; 4 Point () {} 5 Point (double x, double y) : x(x), y(y) {} 6 }; 7 typedef Point Vector;
运算（二维）
- 加法：$vec{v1}+vec{v2}=(x1+x2,y1+y2)$
- 减法：$vec{v1}-vec{v2}=(x1-x2,y1-y2)$
- 内积（点积） $vec{v1} cdot vec{v2} = |v1||v2| cos<v1,v2> =x1x2+y1y2$ 可用来判垂直（=0）或判夹角是锐角(>0)还是钝角(<0)
- 外积（叉积）$vec{v1} imes vec{v2} = |v1||v2| sin<v1,v2> = x1y2-x2y1$
- 叉积的用处：通过它的符号判断两矢量相互之间的顺逆时针关系：如果$vec{v1} imes vec{v2}$为正，则$vec{v1}$逆时针旋转可遇到$vec{v2}$。如果为0则共线，可能同向或反向 另一个用处就是叉积的值是面积
直线
直线的存储
- 为了方便计算通常是用四个double来存储（用一个点和一个向量来表示）（以下点为(x,y),向量为(x1,y1)，$vec{v}$ ）
点到直线的距离
- 设点为(x0,y0)，向量$vec{v0}=(x-x0,y-y0)$，则距离：$frac{vec{v} imes vec{v0} }{ |vec{v}| }$
点是否在直线上
- 距离为0就在直线上，，，
直线的交点
- 设交点为（x,y），直线1点为(x1,y1),向量为(x2,y2)。 直线2点为(x3,y3),向量为(x4,y4)。
- 列得方程 (x-x1)y2=(y-y1)x2 (x-x3)y4=(y-y3)x4
线段
是否相交
- 线段为p1,q1和p2,q2。则若$(p1-q1) imes (p1-q2) * (p1-q1) imes (p1-p2) <0 $ 并且 $ (p2-q2) imes (p2-q1) * (p2-q2) imes (p2-p1) <0 $则相交
多边形
点在多边形内还是多边形外
- 设多边形是由n个点给出（顺时针或者逆时针）
- 角度和判别法，如果在内，则角度和为360，否则不在（好写，但有精度问题）
- 以该点作一条无限长的直线，看穿过多边形几次（很多特殊情况要考虑）
多边形面积
- 用多边形里面的一个点把多边形分成n个三角形，用叉积求面积，全部加起来即可（非凸多边形也可，叉积有正负）