计算集合——叉积&&叉积应用

代码实现：

struct point{
 double x , y;
} 
struct line{
  point a , b ;
}
double Dot(Vector A,Vector B) { return A.x*B.x+A.y*B.y; }  //点积 
double Length(Vector A) { return sqrt(Dot(A,A)); }         //向量长度 
double Angle(Vector A,Vector B) { return acos(Dot(A,B))/Length(A)/Length(B); }  //向量夹角 

double Cross(Vector A,Vector B) { return (A.x*B.y-A.y*B.x); }  // 叉积 
double Area2(Vector A,Vector B,Vector C)  { return Cross(B-A,C-A); }
Vector Rotate(Vector A,double rad)   //向量逆时针旋转 
{
    return Vector(A.x*cos(rad)-A.y*sin(rad),A.x*sin(rad)+A.y*cos(rad));
}
bool Converxline(Vector A,Vector B,Vector C,Vector D)  //两线段是否想交 
{
    //共线或平行
    if((Area2(A,B,C)==0&&Area2(A,B,D)==0) || Area2(A,B,C)*Area2(A,B,D)>0||Area2(C,D,A)*Area2(C,D,B)>0)
        return false;
    else
        return true;
}

View Code

叉积的应用

通过结果的正负判断两矢量之间的顺逆时针关系
若 a x b > 0表示a在b的顺时针方向上
若 a x b < 0表示a在b的逆时针方向上
若 a x b == 0表示a在b共线，但不确定方向是否相同

const double eps = 1e-10;
//考虑误差的加法
double add(double a, double b) {
    if(fabs(a + b) < eps * (fabs(a) + fabs(b))) return 0;
    return a + b;
}
//考虑误差的与0比较
int dcmp(double x) {
    if(fabs(x) < eps) return 0;
    else return x<0?-1:1;
}
struct P {
    double x, y;
    P(){}
    P(double x, double y) :x(x), y(y){}
    bool operator == (P p) {
        return dcmp(x - p.x) == 0 && dcmp(y - p.y) == 0;
    }
    P operator + (P p) {
        return P(add(x, p.x), add(y, p.y));
    }
    P operator - (P p) {
        return P(add(x, -p.x), add(y, -p.y));
    }
    P operator * (double p) {
        return P(x * p, y * p);
    }
    P operator / (double p) {
        return P(x / p, y / p);
    }
    //点积
    double dot(P p) {
        return add(x * p.x, y * p.y);
    }
    //叉积
    double cross(P p) {
        return add(x * p.y, -y * p.x);
    }
};
typedef P Vector;
//向量逆时针旋转
Vector Rotate(Vector a,double rad)  {
    return Vector(a.x * cos(rad) - a.y * sin(rad), a.x * sin(rad) + a.y * cos(rad));
}
//向量的模
double len(Vector a){
    return sqrt(a.dot(a));
}
//两向量的夹角
double angle(Vector a, Vector b) {
    return acos(a.dot(b) / len(a) / len(b));
}
//绝对值为三点确定的三角形的面积的两倍
double area2(Vector a, Vector b, Vector c) {
    return (b - a).cross(c - a);
}
//判断p点是否在线段a-b上
bool on_seg(P p, Vector a, Vector b) {
    return (a - p).cross(b - p) == 0 && (a - p).dot(b - p) <= 0;
}
//判断两条线段是否相交
bool intersect(Vector a, Vector b, Vector c, Vector d) {
    if(area2(a, b, c) == 0 && area2(a, b, d) == 0
    || area2(a, b, c) * area2(a, b, d) > 0
    || area2(c, d, a) * area2(c, d, b) > 0) return false;
    return true;
}
//判断两条线段是否有交点
bool _intersect(Vector a, Vector b, Vector c, Vector d) {
    if(area2(a, b, c) == 0 && area2(a, b, d) == 0 && !on_seg(a, c, d) && !on_seg(b, c, d)
    || area2(a, b, c) * area2(a, b, d) > 0
    || area2(c, d, a) * area2(c, d, b) > 0) return false;
    return true;
}
//极角排序,建议用long long
bool anglecmp(P a, P b) {
    if(a.y <= 0 && b.y > 0) return true;
    if(a.y > 0 && b.y <= 0) return false;
    if(!a.y && !b.y) return a.x < b.x;
    return a.cross(b) > 0;
}

View Code

计算多边形面积(利用向量叉乘)

struct Point { // 点结构体
    int x, y;
};

// 点的叉乘: AB * AC
int cross(const Point &A, const Point &B, const Point &C) {
    return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);
}
/*
 * 计算多边形面积
 * 参数：n个顶点， 多边形顶点坐标集合
 */
double polygon_area(const int &n, Point p[])
{
    double area = 0.0;
    int i;
    Point temp;

    temp.x = temp.y = 0;//原点
    for (i = 0; i < n-1; ++i){
        area += cross(temp, p[i], p[i+1]);
    }
    area += cross(temp, p[n-1], p[0]);//首尾相连
    area = area/2.0;        //注意要除以2
    return area > 0 ? area : -area;    //返回非负数
}

View Code