玩具问题

解题思路：

本题用 $n$ 个纸板将盒子分成 $n+1$ 个区域，然后统计一下每个区域内的玩具数量。

由于每个玩具不会在纸板上，也不会在盒子外，因此我们不需要判断非法的情况。

我们可以直接枚举每个玩具，看一下这个玩具在哪个区域中，这里是可以二分的，如果我们将每个纸板都看成一个向量，那么如果当前玩具在区域 $x$ 中，则当前玩具一定在区域 $x$ 右边所有向量的左侧，一定在区域 $x$ 左边所有向量的右侧。因此是具有二段性的，我们就可以二分找到每个玩具所在的区域。

我们规定每个向量 $\vec{uv}$ 的方向都是从下往上的

接下来就是如何判断一个点 $p$ 在一个向量 $\vec{uv}$ 的左侧，可以发现如果 $\vec{uv} \times \vec{up} >0 0$，说明 $p$ 一定在 $\vec{uv}$ 的左侧。否则说明不在左侧。

C++ 代码

#include <iostream>
#include <cstring>

#define x first
#define y second

using namespace std;

typedef long long LL;
typedef pair<LL, LL> PLL;

const int N = 5010;

int n, m;
PLL a[N], b[N]; //a[i] 表示第 i 个木板的上方点，b[i] 表示第 i 个木板的下方点
int res[N]; //res[i] 表示第 i 个区域的玩具个数

LL cross(LL x1, LL y1, LL x2, LL y2) //求 x1y1 和 x2y2 的叉积
{
    return x1 * y2 - x2 * y1;
}

LL area(PLL a, PLL b, PLL c) //求 ab 和 ac 构成的平行四边形的面积
{
    return cross(b.x - a.x, b.y - a.y, c.x - a.x, c.y - a.y); //返回 ab 和 ac 的叉积
}

int find(LL x, LL y) //二分查找 (x, y) 所在区域的编号
{
    int l = 0, r = n;
    while(l < r)
    {
        int mid = l + r >> 1;
        if(area(b[mid], a[mid], {x, y}) > 0) r = mid; //如果叉积 > 0，说明 (x, y) 在第 mid 个区域左侧
        else l = mid + 1;
    }
    return r;
}

int main()
{
    bool is_first = true; //记录是不是第一组测试数据
    while(scanf("%d", &n), n)
    {
        LL x1, y1, x2, y2;
        scanf("%d%lld%lld%lld%lld", &m, &x1, &y1, &x2, &y2);
        for(int i = 0; i < n; i++)
        {
            LL u, l;
            scanf("%lld%lld", &u, &l);
            a[i] = {u, y1}, b[i] = {l, y2};
        }
        a[n] = {x2, y1}, b[n] = {x2, y2}; //将最后一条边作为边界

        if(is_first) is_first = false;
        else puts("");

        memset(res, 0, sizeof res); //初始化答案
        while(m--)
        {
            LL x, y;
            scanf("%lld%lld", &x, &y);
            res[find(x, y)]++; //更新答案
        }
        for(int i = 0; i <= n; i++) printf("%d: %d\n", i, res[i]);
    }
    return 0;
}