POJ 2318 TOYS：二分查找判斷玩具所在分區

題目大意

矩形區域由 n 條線段（連接上邊 (x1, y1) 與下邊 (x2, y2)）劃分為 n+1 個縱向分區。給 m 個玩具座標，統計每個分區內的玩具數量。線段不相交，n ≤ 5000, m ≤ 5000。

解題思路

1. 所有線段共享相同的 y1, y2，故只需存儲上邊 x 座標與下邊 x 座標。
2. 對於玩具 (x, y)，需找到它位於哪兩條線段之間。利用叉積判斷點在線段左側還是右側。
    向量 AB = (x2 - x1, y2 - y1), AP = (x - x1, y - y1)，叉積 AB × AP > 0 表示 P 在線段左側。
3. 因線段不相交且已按左到右排序，可對線段進行二分查找，找到最後一條使玩具在其左側的線段，該玩具屬於該線段右側的分區（編號為該線段索引）。
4. 特殊情況：玩具在最左側線段左側 → 分區 0；在最右側線段右側 → 分區 n。

代碼實現

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5005;

struct Line { int x1, x2; } L[MAXN];
int cnt[MAXN];

// 叉積判斷點 (x,y) 相對線段 i 的位置：>0 左側, <0 右側
int cross(int i, int x, int y) {
    int x1 = L[i].x1, x2 = L[i].x2;
    return (x2 - x1) * (y - y1) - (x - x1) * (y2 - y1);
}

int main() {
    int n, m, x1, y1, x2, y2;
    while (scanf("%d", &n), n) {
        scanf("%d%d%d%d%d", &m, &x1, &y1, &x2, &y2);
        for (int i = 1; i <= n; ++i) scanf("%d%d", &L[i].x1, &L[i].x2);
        memset(cnt, 0, sizeof(cnt));
        for (int i = 0; i < m; ++i) {
            int x, y; scanf("%d%d", &x, &y);
            if (cross(1, x, y) < 0) { cnt[0]++; continue; }
            if (cross(n, x, y) > 0) { cnt[n]++; continue; }
            int l = 1, r = n;
            while (r - l > 1) {
                int mid = (l + r) >> 1;
                if (cross(mid, x, y) < 0) r = mid;
                else l = mid;
            }
            cnt[l]++;
        }
        for (int i = 0; i <= n; ++i) printf("%d: %d\n", i, cnt[i]);
        if (n) printf("\n");
    }
    return 0;
}

關鍵細節

• 叉積公式簡化：因所有線段共用 y1, y2，可預先計算 dy = y2 - y1。
• 二分邊界條件：r - l > 1 終止，最終 l 為目標分區左邊線段索引。
• 輸出格式：每測資間空行，分區編號從 0 到 n。

複雜度

• 每玩具二分 O(log n)，總 O(m log n)，極快。
• 空間：O(n)。