【模板】计算几何基础

一、点乘
设两向量(Xa,Ya),(Xb,Yb)
则两向量的点乘为XaXb+YaYb
两向量的点乘=两向量长度乘积×cos两向量夹角
由此可利用点乘求出向量长度，以及两向量夹角
len=sqrt(Xa² +Ya²)
ang=arccos[(XaXb+YaYb)/(sqrt(Xa² +Ya²)*(sqrt(Xb² +Yb²)))

转化为代码如下

typedef struct node
{
    double x;
    double y;
}vec,point;

double Dot(vec a,vec b)
{
    return(a.x*b.x+a.y*b.y);
}

double Len(vec a)
{
    return sqrt(a.x*a.x+a.y*a.y);
}

double Ang(vec a,vec b)
{
    return acos(Dot(a,b)/(Len(a)*Len(b)));
}

注：acos()函数作用是求arccos，结果按弧度输出，转化为角度还得乘上约57.3

二、叉乘
设两向量(Xa,Ya),(Xb,Yb)
则两向量的叉乘为XaYb-XbYa，一下记为cross(a,b)
叉乘的绝对值的几何意义为两向量所确定的平行四边形面积
其中，当b在a的逆时针方向时，cross(a,b)>0,在顺时针方向时cross(a,b)<0
该性质可用于判断点和直线的的位置关系
叉乘代码:

double cross(vec a,vec b)
{
    return a.x*b.y-a.y*b.x;
}

三、向量的旋转
向量(x,y)绕起点逆时针旋转θ度，得到新向量(x’,y’)
则x‘=xcosθ-ysinθ
y’=xsinθ+ycosθ

代码如下

vec turn(vec a,double rad)
{
    vec res;
    res.x=a.x*cos(rad)-a.y*sin(rad);
    res.y=a.x*sin(rad)+a.y*cos(rad);
    return res;
}

四、多边形面积
基本思路:将多边形分割成一个个小三角形，利用叉乘求其面积
推广：由于叉乘的有向性，可以从平面内任意一点向多边形各个顶点连线，求所得各个三角形面积和，一个小三角形计入的多余部分会被其他小三角形计入的多余部分正负抵消掉(此处不会证明，直接记结论)
因此不妨取多边形的一点为分割点
代码如下

double area(point p[],int n)
{
    double res=0;
    for(int i=1;i<n-1;i++)
    	{
            vec a,b;
            a.x=p[i].x-p[0].x;a.y=p[i].y-p[0].y;
            b.x=p[i+1].x-p[0].x;b.y=p[i+1].y-p[0].y;
            res+=cross(a,b);
        }
    return res/2;
}