POJ 2318 玩具分箱：叉積判斷點線關係 + 二分查找

問題描述

矩形盒子被 n 塊木板分成 n+1 個格子。木板連接上邊 (U_i, y1) 和下邊 (L_i, y2)，按 x 坐標從左到右排序。m 個玩具隨機拋入，求每個格子內玩具數量。n, m ≤ 5000。

幾何核心：叉積判斷點在線段哪側

對於木板 i，向量 **v1** = (U_i - L_i, y1 - y2)（木板方向），向量 **v2** = (x - L_i, y - y2)（木板下端點到玩具）。叉積 **v1** × **v2** = (U_i - L_i)(y - y2) - (x - L_i)(y1 - y2)。

• 叉積 > 0：玩具在木板左側
• 叉積 < 0：玩具在木板右側
• 叉積 = 0：玩具在木板上（題目保證不發生）

算法流程

1. 讀入木板坐標，按題目保證已排序
2. 對每個玩具 (x, y)，在木板數組上二分查找：找到第一個使玩具在其左側的木板索引 pos
3. 玩具屬於第 pos-1 個格子（0-indexed），計數器 `sum[pos-1]++`
4. 輸出 0 到 n 共 n+1 個格子的計數

關鍵代碼（C++）

double U[M], L[M]; // 木板上下端點 x 坐標
int sum[M];
double y1, y2; // 盒子上下邊 y 坐標

bool leftOf(int mid, double x, double y) { // 判斷點是否在 mid 木板左側
    double v1x = U[mid] - L[mid];
    double v1y = y1 - y2;
    double v2x = x - L[mid];
    double v2y = y - y2;
    return v1x * v2y - v2x * v1y >= 0; // 叉積 >= 0 表示左側或共線
}

int findBin(double x, double y) {
    int l = 1, r = n, mid;
    while (l <= r) {
        mid = (l + r) >> 1;
        if (leftOf(mid, x, y)) r = mid - 1;
        else l = mid + 1;
    }
    return l; // 返回第一個在左側的木板索引
}

int main() {
    while (scanf("%d", &n), n) {
        scanf("%d%lf%lf%lf%lf", &m, &x1, &y1, &x2, &y2);
        for (int i = 1; i <= n; ++i) scanf("%lf%lf", &U[i], &L[i]);
        memset(sum, 0, sizeof(sum));
        for (int i = 0; i < m; ++i) {
            double x, y; scanf("%lf%lf", &x, &y);
            int pos = findBin(x, y);
            sum[pos - 1]++;
        }
        for (int i = 0; i <= n; ++i) printf("%d: %d\n", i, sum[i]);
    }
    return 0;
}

精度關鍵

• 坐標範圍未明確，但叉積計算涉及減法，需用 `double` 避免精度丟失
• 題目提示：`double` 過，`long long` WA，說明坐標可能非整數或中間計算超出 64 位整數範圍

複雜度分析

• 每玩具二分查找：O(log n)
• 總時間：O(m log n)，n,m=5000 時極快
• 空間：O(n)

此題是計算幾何與二分查找結合的經典應用，叉積判斷點線關係是核心幾何工具，木板有序性使二分成為可能。