POJ 2318 TOYS：二分查找確定玩具落入隔板編號

POJ 2318 TOYS：二分查找確定玩具落入隔板編號

矩形玩具箱內有 n 條不相交的紙板隔板（左端 (U_i, y1)，右端 (L_i, y2)），從左到右有序。m 個玩具隨機拋入箱內（不落在邊界），統計每個格子（0..n）的玩具數。n, m ≤ 5000。

幾何判斷

隔板 i 的直線方程：x = U_i + (L_i - U_i) * (y1 - y) / (y1 - y2)。玩具 (X, Y) 在隔板左側當 X < x_i(Y)。因隔板有序，可對玩具的 X 座標在隔板交點處二分查找，確定落入第幾格。

算法流程

1. 讀入隔板端點座標。
2. 對每個玩具，二分查找最小的隔板索引 k 使得 X < x_k(Y)，則玩具落在格子 k（0-based）。
3. 統計各格子計數，輸出。

關鍵代碼邏輯

double getX(int i, double y) {
    return U[i] + (L[i] - U[i]) * (y1 - y) / (y1 - y2);
}
int findBin(double X, double Y) {
    int l = 0, r = n;
    while (l < r) {
        int mid = (l + r) >> 1;
        if (X < getX(mid, Y)) r = mid;
        else l = mid + 1;
    }
    return l; // 0..n
}

複雜度

• 時間：O(m log n) ≈ 5000 * 13，極快。
• 空間：O(n)。

本題核心是利用隔板有序性將點位問題轉化為二分查找，避免了 O(n*m) 暴力判斷，是計算幾何與二分結合的經典例題。