POJ 1584：A Round Peg in a Ground Hole - 凸多邊形判定與圓內切

問題描述

給定多邊形頂點 (按順序)，判斷：1) 是否為凸多邊形 (無凹陷)；2) 若是凸多邊形，給定圓心 (pegX, pegY) 和半徑 pegR，圓是否完全在多邊形內 (含邊界)。

凸多邊形判定

對任意連續三點 A, B, C，叉積 cross(B-A, C-B) 符號必須相同 (全正或全負，視順序方向)。若有符號不同則為凹多邊形 (ILL-FORMED)。

圓在凸多邊形內判定

1. 圓心是否在多邊形內：對每條邊 AB，叉積 cross(B-A, O-A) 符號與多邊形方向一致 (嚴格內部可允許 0)。
2. 圓心到每條邊的距離 ≥ 半徑：距離 = |cross(B-A, O-A)| / |B-A|。

代碼實現

#include <bits/stdc++.h>
using namespace std;
const double EPS = 1e-8;

struct Pt { double x, y; };
Pt operator-(Pt a, Pt b) { return {a.x-b.x, a.y-b.y}; }
double cross(Pt a, Pt b) { return a.x*b.y - a.y*b.x; }
double len(Pt a) { return hypot(a.x, a.y); }

int sgn(double x) { if (x > EPS) return 1; if (x < -EPS) return -1; return 0; }

int main() {
    int n;
    while (cin >> n, n >= 3) {
        double R, cx, cy; cin >> R >> cx >> cy;
        vector p(n);
        for (auto &pt : p) cin >> pt.x >> pt.y;
        p.push_back(p[0]); // 封閉

        // 1. 判斷凸性
        int dir = 0;
        bool convex = true;
        for (int i = 1; i < n; ++i) {
            int cr = sgn(cross(p[i]-p[i-1], p[i+1]-p[i]));
            if (cr != 0) {
                if (dir == 0) dir = cr;
                else if (dir != cr) { convex = false; break; }
            }
        }
        if (!convex) { cout << "HOLE IS ILL-FORMED\n"; continue; }

        // 2. 圓心在內部
        Pt O = {cx, cy};
        bool inside = true;
        for (int i = 0; i < n; ++i) {
            int cr = sgn(cross(p[i+1]-p[i], O-p[i]));
            if (cr != dir) { inside = false; break; }
        }
        if (!inside) { cout << "PEG WILL NOT FIT\n"; continue; }

        // 3. 到各邊距離 >= R
        bool fit = true;
        for (int i = 0; i < n; ++i) {
            double d = fabs(cross(p[i+1]-p[i], O-p[i])) / len(p[i+1]-p[i]);
            if (d + EPS < R) { fit = false; break; }
        }
        cout << (fit ? "PEG WILL FIT" : "PEG WILL NOT FIT") << '\n';
    }
    return 0;
}

關鍵點

• 叉積符號判斷凸性與點在多邊形內 (同向性)。
• 點到線段距離公式：|cross(v, w)| / |v|。
• 輸入以 n < 3 結束。

總結

計算幾何基礎題：凸多邊形判定 + 圓內切檢查。叉積是核心工具，同時用於方向判斷、點在多邊形內、點到線距離。