前提条件
1 |
|
点(向量)
已知
(x,y),点坐标或向量坐标
函数
相加、相减、与常数相加、点乘、叉乘、旋转、标准化
向量旋转
[cosθ−sinθsinθcosθ][xy]=[xcosθ−ysinθxsinθ+ycosθ]代码
1 | // 点或向量 |
极坐标点
1 | struct polar{ |
线段
已知
已知线段两端端点A,B
函数
跨立实验,快速排斥实验
代码
1 | // 线段 |
直线与射线
已知
已知直线上一点和向量,P,→s
函数
获得直线上的一点
求两直线交点

公式
P=A−→b⋅→BA→b⋅→a⋅→a代码
1 | struct line{ |
圆
已知
圆心O,半径r
代码
1 | struct circle{ |
直线与圆

已知
直线:P点坐标(Px,Py),→s=(sx,sy)
圆:O点坐标(Ox,Oy),圆的半径r
推导
|OE|=→s×→PO|→s||PE|=→s⋅→PO|→s||AE|=|BE|=√r2−|OE|2|PA|=|PE|−|AE||PB|=|PE|+|BE|A=P+|PA||→s|⋅→sB=P+|PB||→s|⋅→s代码
1 | seg intersectionOfLineAndCircle(const line& p, const cle& c){ |
凸包
已知
已知一个二维坐标图中每个顶点,求最小周长能够包含所有所有顶点的凸包
思路
先将点双关键字排序,横坐标为第一关键字,纵坐标为第二关键字
排序之后

图片向量方向迭代方向
之后维护单调单调栈,其中栈顶为S1,栈顶第二元素为S2,当前检查的点为P,由于凸包是不会出现右转的,所以当出现→S2S1×→S1P<0说明栈顶的元素不是最优凸包,弹出栈顶重复上一步。



第一次循环迭代之后,会发现求完了下凸包先在需要倒转迭代方向,再次遍历




第二次迭代完善上凸包,最终会形成一个最短周长的能够包含所有顶点的凸包
注意:运行结果最后还会添加一次初始节点,那么周长就为∑tp−1i=0|→pipi+1|
代码
1 | const int N = 1e5+10; |
作者: Csome