前排碎碎念
大抵就是些与坐标系，向量有关的东西。难度不大，但是很杂，遂整理。
向量运算
A(a.x,a.y),B(b.x,b.y)
加法：
A+B=(a.x+b.x , a.y+b.y)
减法:
A-B=(a.x-b.x , a.y-b.y)
点积：
- a·b=|a||b|cos<a,b> =x1x2 + y1y2
- 向量b在向量a上的投影与a长度的乘积
- 应用：判断两向量垂直/平行
求两向量夹角
叉积：
- a x b = |a||b|sin<a,b>
= x1y2-y1x2 - 几何意义：向量a与b张成的平行四边形的有向面积 顺正逆负
- 应用：判断点线的位置关系：
（b-a) x (c-a) > 0 c在直线ab的左侧，反之在直线右侧 - 判断线线的位置关系：
直线ab与线段cd无交点：c与ab叉积 x d与ab叉积 >0
即两点在直线同侧 - 求两直线的交点（点向式）
double t=(a-b)·v/(v·u);
return a+ut;
极坐标
构成：
一个定点O：极点；一条从O引出的射线：极轴；一个单位长度与单位角度与正方向
极坐标下点的表示
有序数对（极径，极角）
同一个点可以有多个有序数对表示（角度相差2kΠ），同一个极坐标表示的点是唯一确定的
对于Cpp，调用atan2(y,x)获得极角，极径即为sqrt(x^2 + y^2)
空间球坐标系
坐标描述与实际位置：球坐标(a,b,c)为 距离球心距离为a，垂直向下偏转b°，水平逆向偏转c°的点
二维平面中元素的表示：
点：pair；向量：pair；直线：点向；线段：记录两端点坐标
多边形：按照一定顺序记录多边形的每个顶点
基本公式
正弦定理，余弦定理
一些基本操作
- 快速排斥实验：简单粗筛
- 跨立实验：一个线段的两个端点在另一个线段的两端
- 判断一点在多边形内部:
光线投射算法：从该点为端点引出一条射线，该射线每次与多边形的一条边相交，就切换一次与多边形的内外关系 奇内偶外
回转数算法：把该点与多边形的所有顶点连接起来，计算相邻两边夹角的和。注意这里的夹角是 有方向的。如果夹角和为 0，则这个点在多边形外，否则在多边形内 - 求任意多边形的面积
利用 叉积 进行运算 取多边形上的点逆时针标记为p1...Pn，任选一个辅助点O，记向量vi=pi-O，那么多边形的面积为 求和 vi x v(i%n+1) /2 - 圆与直线交点：
勾股定理 - 两圆交点：
两个交点： 将一圆圆心与交点相连，求出两圆心连线与该连线所成角。这样，将两圆心连线的方向向量旋转这个角度，就是圆心与交点相连形成的半径的方向向量了。最后沿方向向量方向将圆心平移半径长度。
一个交点：在圆心的连线上