一、题意分析

背景与问题：John 的父母为了让 John 的玩具能更好地分类存放，在一个长方形的玩具盒中放置了若干纸板隔板将其分成不同的区间。现在需要根据玩具的投放位置，计算每个区间内落入的玩具数量。

输入信息： 输入包含一个或多个问题，每个问题的第一行有六个整数 n m x1 y1 x2 y2。其中 n 表示纸板隔板的数量（0 < n <= 5000），m 表示玩具的数量（0 < m <= 5000），(x1, y1) 是玩具盒左上角的坐标，(x2, y2) 是玩具盒右下角的坐标。 接下来 n 行，每行包含两个整数 Ui Li，表示第 i 个纸板隔板的两个端点坐标分别为 (Ui, y1) 和 (Li, y2)，且隔板按从左到右的顺序指定，且彼此不相交。 再接下来 m 行，每行包含两个整数 Xj Yj，表示第 j 个玩具的位置，且玩具位置顺序随机，且不会落在纸板隔板上或盒子边界之外。 输入以单独一行的 0 结束。 输出要求：对于每个问题，输出每个区间（从左到右编号为 0 到 n）的玩具数量，格式为 区间编号: 玩具数量，不同问题的输出之间用一个空行分隔。

二、解题思路

数据结构定义： 使用结构体 Point 来表示点的坐标，包含 x 和 y 两个成员变量。 使用结构体 Line 来表示纸板隔板，每个隔板由两个点 a 和 b 组成。 定义数组 cnt[5005] 来记录每个区间内玩具的数量。 计算叉积函数 Multi：该函数用于计算向量 p0p1 和 p0p2 的叉积，通过叉积的正负可以判断点 p1 相对于向量 p0p2 的位置（在左侧还是右侧）。叉积公式为 (p1.x - p0.x) * (p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y)。

二分查找函数 BSearch： 对于给定的玩具位置点 a，通过二分查找的方式确定它位于哪个区间。 初始时，设置查找区间为 [0, n - 1]，每次取中间位置 mid，计算点 a 相对于中间隔板 line[mid] 的叉积。 如果叉积大于 0，说明点 a 在隔板的右侧，更新左边界 l = mid + 1；否则更新右边界 r = mid。 当 l < r 的循环结束后，再根据点 a 相对于最终确定的隔板的叉积情况，确定将玩具计数加在该隔板左侧还是右侧的区间内。

主函数 main： 循环读取每个问题的输入，直到输入为 0 结束。 读取纸板隔板数量 n、玩具数量 m 以及玩具盒的坐标范围。 读取每个纸板隔板的端点坐标，构建 line 数组。 初始化 cnt 数组为 0。 读取每个玩具的坐标，调用 BSearch 函数确定其所在区间并计数。 最后按格式输出每个区间的玩具数量，并在不同问题的输出之间输出一个空行。

三、代码实现细节

输入处理：使用 scanf 函数按顺序读取输入数据，确保数据的正确读取和处理。

二分查找：在 BSearch 函数中，通过二分查找快速定位玩具所在区间，提高算法效率。查找结束后，根据叉积的最终判断结果正确更新玩具计数。 输出处理：按照题目要求的格式，使用 printf 函数输出每个区间的玩具数量，并且在不同问题的输出之间添加一个空行。

参考代码

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

struct Point {
    int x, y;
};

struct Line {
   Point a, b;
} line[5005];

int cnt[5005];

int Multi(Point p1, Point p2, Point p0) {
    return (p1.x - p0.x) * (p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y);
}

void BSearch(Point a, int n) {
    int l, r, mid;
    l = 0; r = n-1;
    while (l < r) {
        mid = (l + r) >> 1;
        if (Multi(a, line[mid].a, line[mid].b) > 0) l = mid + 1;
        else r = mid;
    }
    if (Multi(a, line[l].a, line[l].b) < 0) cnt[l]++;
    else cnt[l+1]++;
}

int main()
{
    int n, m, x1, y1, x2, y2;
    int i, t1, t2;
    Point a;
    while (scanf ("%d", &n) && n) {
        scanf ("%d%d%d%d%d", &m, &x1, &y1, &x2, &y2);
        for (i = 0; i < n; i++) {
            scanf ("%d%d", &t1, &t2);
            line[i].a.x = t1;
            line[i].a.y = y1;
            line[i].b.x = t2;
            line[i].b.y = y2;
        }
        memset(cnt, 0, sizeof (cnt));
        for (i = 0; i < m; i++) {
            scanf ("%d%d", &a.x, &a.y);
            BSearch(a, n);
        }
        for (i = 0; i <= n; i++)
            printf ("%d: %d\n", i, cnt[i]);
        printf("\n");
    }
    return 0;
}