向量叉積幾何意義與應用：判斷順逆時針、多邊形面積與凸包

定義與計算

給定二維向量 P(x1, y1) 與 Q(x2, y2)，其**叉積**（Cross Product）定義為標量：

P × Q = x1·y2 - x2·y1

幾何意義：結果的**絕對值**等於以兩向量為邊的平行四邊形面積；**正負號**表示旋轉方向。

核心性質：判斷相對方位

應用一：多邊形頂點序列方向判斷

給定多邊形頂點 p[0]...p[n-1]（按順序），計算所有**連續邊向量**的叉積和：

long long sum = 0;
for (int i = 0; i < n; ++i) {
    Point a = p[i];
    Point b = p[(i+1)%n];
    Point c = p[(i+2)%n];
    // 向量 AB × BC
    sum += (b.x - a.x) * (c.y - b.y) - (b.y - a.y) * (c.x - b.x);
}
// 或直接累加 (p[i] × p[i+1])
for (int i = 0; i < n; ++i)
    sum += cross(p[i], p[(i+1)%n]);

• sum > 0：頂點為**順時針**序
• sum < 0：頂點為**逆時針**序
• |sum| / 2 即為多邊形面積（鞋帶公式）

應用二：線段相交判斷（跨立實驗）

線段 AB 與 CD 相交 ⇔ cross(AC, AD) * cross(BC, BD) ≤ 0 且 cross(CA, CB) * cross(DA, DB) ≤ 0。利用叉積符號判斷端點是否分佈在另一線段兩側。

應用三：凸包算法

Graham Scan 核心步驟：

1. 找最低最左點作為極點
2. 其餘點按極角排序
3. 掃描時維護棧，若新點導致「右轉」（叉積 < 0）則彈出棧頂

叉積符號直接決定保留或移除點，構建凸包。

C++ 實用工具類

struct Point {
    long long x, y;
    Point() {}
    Point(long long _x, long long _y) : x(_x), y(_y) {}
    Point operator-(const Point& o) const { return Point(x - o.x, y - o.y); }
};

long long cross(const Point& a, const Point& b) {
    return a.x * b.y - a.y * b.x;
}
long long cross(const Point& a, const Point& b, const Point& c) {
    return cross(b - a, c - a); // AB × AC
}

常見坑點提醒

1. 整數溢位：座標範圍大時用 long long 或 __int128。
2. 共線處理：叉積為 0 時需結合點積判斷同向/反向，或依題目定義決定是否視為相交/在邊上。
3. 座標系差異：螢幕座標系 Y 軸向下，叉積符號與數學座標系相反，需注意轉換。

結語

向量叉積是計算幾何的「瑞士刀」，以極簡代數運算編碼豐富幾何資訊。掌握其符號判斷方位、絕對值算面積的核心，即可輕鬆解決多邊形方向、線段相交、凸包、點在多邊形內等經典問題。