参考博客：http://dev.gameres.com/Program/Abstract/Geometry.htm#

向量的点积

结果为$\vec{a}· \vec{b}=x_1x_2+y_1y_2$。

点积的结果是一个数值。

点积的集合意义：我们以向量 a 向向量 b 做垂线，则$| a |*cos(a,b)$为 a 在向量 b 上的投影，即点积是一个向量在另一个向量上的投影乘以另一个向量。且满足交换律

应用：可以根据集合意义求两向量的夹角，$\vec{a}·\vec{b}=|\vec{a}||\vec{b}|cos\theta$。

向量的叉积

结果为$|\vec{a}\times\vec{b}|=|\vec{a}||\vec{b}|sin\theta=x1*y2-x2*y1$。

叉积的结果也是一个向量，是垂直于向量a，b所形成的平面，如果看成三维坐标的话是在 z 轴上，上面结果是它的模。

方向判定：右手定则，（右手半握，大拇指垂直向上，四指右向量a握向b，大拇指的方向就是叉积的方向）

坐标运算：

$\vec{a}=a_x,a_y,a_z$，$\vec{b}=b_x,b_y,b_z$ ，i,j,k分别是X,Y,Z轴方向的单位向量，则$\vec{a}×\vec{b}=(a_yb_z-a_zb_y)\vec{i}+(a_zb_x-a_xb_z)\vec{j}+(a_xb_y-a_yb_x)\vec{k}$,

为了帮助记忆,利用三阶

行列式，写成

det 。

$a\times b=(l,m,n)\times (o,p,q)=(mq-np,no-lq,lp-mo)$。

叉积的集合意义：

1：其结果是a和b为相邻边形成平行四边形的面积。

2：结果有正有负，有sin（a，b）可知和其夹角有关，夹角大于180°为负值。

3：叉积不满足交换律

应用：

1：通过结果的正负判断两矢量之间的顺逆时针关系

若 a×b > 0表示a在b的顺时针方向上

若 a×b < 0表示a在b的逆时针方向上

若 a×b == 0表示a在b共线，但不确定方向是否相同

2：判断折线拐向，可转化为判断第三点在前两的形成直线的顺逆时针方向，然后判断拐向。

3：判断一个点在一条直线的哪一侧，同样上面的方法。

4：判断点是否在线段上，可利用叉乘首先判断是否共线，然后在判断是否在其上。

5：判断两条直线是否相交

​ 我们分两步确定两条线段是否相交：

​ (1)快速排斥试验

​ 设以线段 P1P2 为对角线的矩形为R， 设以线段 Q1Q2 为对角线的矩形为T，如果R和T不相交，显然两线段不会相交。

　 (2)跨立试验
　 如果两线段相交，则两线段必然相互跨立对方。若P1P2跨立Q1Q2 ，则矢量 ( P1 - Q1 ) 和( P2 - Q1 )位于矢量( Q2 - Q1 ) 的两侧，即( P1 - Q1 ) × ( Q2 - Q1 ) ( P2 - Q1 ) × ( Q2 - Q1 ) < 0。上式可改写成( P1 - Q1 ) × ( Q2 - Q1 ) ( Q2 - Q1 ) × ( P2 - Q1 ) > 0。当 ( P1 - Q1 ) × ( Q2 - Q1 ) = 0 时，说明 ( P1 - Q1 ) 和 ( Q2 - Q1 )共线，但是因为已经通过快速排斥试验，所以 P1 一定在线段 Q1Q2上；同理，( Q2 - Q1 ) ×(P2 - Q1 ) = 0 说明 P2 一定在线段 Q1Q2上。所以判断P1P2跨立Q1Q2的依据是：( P1 - Q1 ) × ( Q2 - Q1 ) ( Q2 - Q1 ) × ( P2 - Q1 ) >= 0。同理判断Q1Q2跨立P1P2的依据是：( Q1 - P1 ) × ( P2 - P1 ) ( P2 - P1 ) × ( Q2 - P1 ) >= 0。

具体情况如下图所示：

​

//这里直线1的两个顶点是p[0],p[1];直线2的两个顶点是p[2],p[3]。
struct point
{
    double x,y;
}p[5];
double calc(point a,point b,point c)
{
    return a.x*b.y+b.x*c.y+c.x*a.y-a.x*c.y-b.x*a.y-c.x*b.y;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        for(int i=0;i<4;i++)
            scanf("%lf%lf",&p[i].x,&p[i].y);
        double l0102=calc(p[0],p[1],p[2]);
        double l0103=calc(p[0],p[1],p[3]);
        double l2320=calc(p[2],p[3],p[0]);
        double l2321=calc(p[2],p[3],p[1]);
        if(l0102*l0103<=0&&l2320*l2321<=0)printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

混合积

设 a ,b,c 是空间中三个向量，则 (a×b)·c称为三个向量 a ，b ，c 的混合积，记作[a b c] 或 (a,b,c) 或 (abc)。

设$\vec{a}=a_1\vec{i}+a_2\vec{j}+a_3\vec{k}$，$\vec{b}=b_1\vec{i}+b_2\vec{j}+b_3\vec{k}$，$\vec{c}=c_1\vec{i}+c_2\vec{j}+c_3\vec{k}$。则有

应用：

四个点构成三个向量， 如果这三个向量的混合积为0，那么体积为0，那么四点共面。

求任意多边形面积-有向面积

只要记住这个公式：

如果逆时针给出点坐标，值为正，

如果顺时针给出点坐标，值为负。

当i=n-1 i+1就是n所代表的点就是第一个点。

struct point
{
    int x,y;
}p[110];
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        if(n==0)break;
        for(int i=0;i<n;i++)
            scanf("%d%d",&p[i].x,&p[i].y);
        p[n].x=p[0].x;p[n].y=p[0].y;
        double ans=0;
        for(int i=0;i<n;i++)
            ans+=0.5*(p[i].x*p[i+1].y-p[i+1].x*p[i].y);
        printf("%.1f\n",ans);
    }
    return 0;
}

皮克公式

给定顶点坐标均是整点（或正方形格点）的简单多边形，皮克定理说明了其面积S和内部格点数目n、边上格点数目s的关系：

(其中n表示多边形内部的点数,s表示多边形边界上的点数,S表示多边形的面积)

poj 1265

题意：给出机器人每一步向右走和向上走的步数，得到一个平面上的简单多边形，求边上的点，多边形内的点，多边形面积。

思路：

先求边上格点数目：已知一条直线，如(5,0)到(6,3)这条直线，经过的整点数是2，可通过如下公式计算：

格点数 = gcd(|x2-x1|,|y2-y1|)

前提，约定起点不算在该线所经过格点数中。

再利用上面求多边形面积的方法求出面积，根据皮克公式可以求出内部格点数目。

struct point
{
    int x,y;
}p[110];
int n;
int gcd(int a,int b)
{
    if(a==0)return b;
    if(b==0)return a;
    if(a<b){int temp;temp=a;a=b;b=temp;}
    while(a%b){int r=a%b;a=b;b=r;}
    return b;
}
double mianji()
{
    double s=0;
    for(int i=0;i<n;i++)
        s+=0.5*(p[i].x*p[i+1].y-p[i+1].x*p[i].y);
    return abs(s);
}
int main()
{
    int t;
    scanf("%d",&t);
    for(int kase=1;kase<=t;kase++)
    {
        scanf("%d",&n);
        int num=0;//边上的格点数
        p[0].x=0;p[0].y=0;
        for(int i=1;i<=n;i++)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            num+=gcd(abs(a),abs(b));
            p[i].x=p[i-1].x+a;
            p[i].y=p[i-1].y+b;
        }
        double ss=mianji();
        printf("Scenario #%d:\n%d %d %.1f\n\n",kase,(int)ss-(num/2)+1,num,ss);
    }
    return 0;
}

精度

参考博客：http://www.cnblogs.com/crazyacking/p/4668471.html

判断浮点数相等：

#define eps 1e-8//依题目而定
int sgn(double x)
{
    if(fabs(x) < eps)return 0;
    if(x < 0)return -1;
    else return 1;
}

凸包

参考博客：https://www.cnblogs.com/aiguona/p/7232243.html

1⃣把纵坐标最小的点作为p0，如果有多个纵坐标最小的点，就选其中横坐标最小的点。

2⃣按逆时针方向相对于p0进行极角排序，如果极角相同，就把距离p0近的排在前面。

3⃣把p0,p1入栈，把p2作为当前点。

4⃣栈顶的上一个到栈顶画一根直线，如果当前点在这根直线的左边或者直线上，该点入栈，如果当前点在这根直线的右边，就让栈顶元素出栈，继续4⃣步骤。

5⃣如果不是最后一个元素，选这个入栈元素后面一个元素为当前点，继续4⃣步骤。

以hdu1392求凸包周长为例（这里注意n=1和n=2要特判（因为没有形成圈））

struct point
{
    double x,y;
}a[110],p[110];
int n,top;
double cross(point p0,point p1,point p2)//叉乘判断在左边还是右边
{
    return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}
double dis(point a,point b)
{
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
bool cmp(point p1,point p2)
{
    double c=cross(a[0],p1,p2);
    if(c>0||(c==0&&dis(a[0],p1)<dis(a[0],p2)))
        return 1;
    return 0;
}
void graham()
{
    int pos=0;//最下最左的点
    for(int i=0;i<n;i++)
        if((a[i].y<a[pos].y)||(a[i].y==a[pos].y&&a[i].x<a[pos].x))
            pos=i;
    swap(a[pos],a[0]);
    sort(a+1,a+n,cmp);//极角排序
    top=1;
    p[0]=a[0];
    p[1]=a[1];//0,1入栈
    for(int i=2;i<n;i++)
    {
        while(top&&cross(p[top-1],p[top],a[i])<0)//栈顶和栈顶的前一个连线，如果当前点在右边的话，栈顶出栈，继续
            top--;
        top++;
        p[top]=a[i];
    }
}
int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        if(n==0)break;
        if(n==1){printf("0.00\n");continue;}
        for(int i=0;i<n;i++)
            scanf("%lf%lf",&a[i].x,&a[i].y);
        if(n==2){printf("%.2f\n",dis(a[0],a[1]));continue;}//因为不成圈所以2要特判
        graham();
        double ans=0;
        p[top+1]=p[0];
        for(int i=0;i<=top;i++)
            ans+=dis(p[i],p[i+1]);
        printf("%.2f\n",ans);
    }
    return 0;
}