计算几何入门
一 向量
我认为唯一比较有用的东西是向量的叉积
1.叉积
a.定义
对于两个0起点开始，最终点为(a1,a2)和(b1,b2)的两个向量，其叉积为a1 * b2 - a2 * b1。
b.应用
可以判断两个向量的旋转方向：
假如A和B的叉积最终得到<0，那么说明A是逆时针旋转到B的，也可以说，B在A的左手边
若得到=0，那么这两个向量是共线的
若得到>0，那么A可以顺时针旋转得到B，也可以说，B在A的右手边
凸包
寻找凸包
算法1:Graham
算法流程：
1.找到一个在左下角的点（优先满足y坐标更小），令其为s
2.对于其他点，使用极角排序，对于极角相同的点离s更小的排在前面。
为了保证精确度，可以用以下代码排序
bool cmp(node p1,node p2)
{
double tmp=check(dot[1],p1,dot[1],p2);
if(tmp>0)
return 1;
if(tmp==0&&dis(dot[1],p1)<dis(dot[1],p2))
return 1;
return 0;
}
其中check/tmp是叉积,dis为距离
3.维护一个栈，保证里面至少要有两个元素（s和dot[2])，对于剩下的n-2个点,尝试将其加入到栈中。
令栈首为A，栈次为B，将加入的为C。
要求AC构成的向量在BA的左侧，可以看以下代码：
for(int i=3;i<=n;i++){
while(top>=2&&pan(s[top],s[top-1],dot[i])==1){
top--;
}
top++;
s[top]=dot[i];
}
其中pan是：
bool pan(node x,node y,node k){//栈头点/栈次点/将要加入的点 ，返回是否要弹出栈头
if(check(k,x,y,x)>0){//左侧
return 0;
}
else{
return 1;//在一条线上的暂时视为删除
}
}