Java 判斷凸多邊形：向量叉積法完整實現 (HDU 2108 範例)

幾何判定原理

多邊形頂點按**逆時針 (或順時針)** 順序給定。對於任意三個連續頂點 P[i], P[i+1], P[i+2] (索引取模)，構建向量：

• v1 = P[i+1] - P[i]
• v2 = P[i+2] - P[i+1]

計算**叉積 (Cross Product)** cross = v1.x * v2.y - v1.y * v2.x：

• cross > 0：左轉 (逆時針凸角)
• cross < 0：右轉 (凹角)
• cross == 0：共線

若**所有叉積同號 (全 ≥ 0 或全 ≤ 0)**，則為凸多邊形；否則為凹多邊形。

完整 Java 代碼 (對應 HDU 2108)

import java.util.Scanner;

public class ConvexPolygonJudge {
    static class Point {
        int x, y;
        Point() {}
        Point(int x, int y) { this.x = x; this.y = y; }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (true) {
            int n = sc.nextInt();
            if (n == 0) break;

            Point[] p = new Point[n];
            for (int i = 0; i < n; i++) {
                int x = sc.nextInt();
                int y = sc.nextInt();
                p[i] = new Point(x, y);
            }

            boolean convex = true;
            for (int i = 0; i < n; i++) {
                int j = i;
                int k = (i + 1) % n;
                int t = (i + 2) % n;

                // 向量 v1 = P[k] - P[j], v2 = P[t] - P[k]
                int v1x = p[k].x - p[j].x;
                int v1y = p[k].y - p[j].y;
                int v2x = p[t].x - p[k].x;
                int v2y = p[t].y - p[k].y;

                int cross = v1x * v2y - v1y * v2x;
                if (cross < 0) { // 逆時針序列應全為非負
                    convex = false;
                    break;
                }
            }

            System.out.println(convex ? "convex" : "concave");
        }
        sc.close();
    }
}

關鍵細節解析

幾何知識擴展：三角形五大中心

本文原始內容亦包含三角形中心計算，補充整理如下：

1. 外心 — 三邊中垂線交點 (外接圓圓心)

• 性質：到三頂點等距
• 向量法：(O-A + O-B)·(A-B) = 0 等 → 解線性方程組
• 代碼：構建兩條中垂線，求交點

2. 內心 — 三角平分線交點 (內切圓圓心)

• 座標公式：I = (a*A + b*B + c*C) / (a+b+c) (a,b,c 為對邊長)
• 半徑：r = 2S / (a+b+c) (S 為面積，海倫公式)

3. 重心 — 三中線交點

• 座標：G = (A + B + C) / 3

4. 垂心 — 三高線交點

• 向量性質：H = A + B + C - 2O (O 為外心)

5. 九點圓圓心 — 外心與垂心中點

常見 OJ 題目變體

• 判斷點在凸多邊形內 (O(log N) 二分法 / O(N) 射線法)
• 凸包構建 (Graham Scan / Andrew 算法 O(N log N))
• 多邊形面積 (鞋帶公式)
• 旋轉卡殼求直徑/寬度

結語

凸多邊形判定是計算幾何入門必修課。**向量叉積** 不僅能判定凸凹，更是「點在多邊形內」、「線段相交」、「凸包構建」等核心問題的基石。掌握整數座標下的叉積運算與取模索引技巧，即可輕鬆應對 ACM/ICPC 類幾何題。