问题分析

我们需要解决的问题是：给定一个矩形盒子，里面有若干垂直的纸板分隔，将盒子分成多个区域。每个玩具被扔进盒子后，会落在某个区域内。我们需要统计每个区域中有多少个玩具，并输出每个玩具数量对应的区域数目。

方法思路

$1、$输入处理：读取每个测试用例的数据，包括盒子的边界、分隔板的位置以及玩具的位置。

$2、$区域划分：根据分隔板的位置，确定每个玩具所在的区域。由于分隔板是垂直的且不相交，可以使用二分法来确定每个玩具位于哪两个分隔板之间。

$3、$统计玩具数量：对于每个区域，统计其中的玩具数量。

$4、$输出结果：按照玩具数量从小到大输出每个数量对应的区域数目。

#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<stack>
#include<cstdio>
#include<vector>
#include<utility>
#include<cctype>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define inf 0x3f3f3f3f
#define Clear(x) memset(x,0,sizeof(x))
#define fup(i,a,b) for(int i=a;i<b;i++)
#define rfup(i,a,b) for(int i=a;i<=b;i++)
#define fdn(i,a,b) for(int i=a;i>b;i--)
#define rfdn(i,a,b) for(int i=a;i>=b;i--)
typedef long long ll;
using namespace std;
const double pi=acos(-1.0);
const int maxn = 1e3+7;
int ans[maxn],num[maxn];
 
struct Point{
    int x,y;
    Point(){}
    Point(int _x,int _y){x=_x;y=_y;}
};
 
struct Line{
    Point a,b;
    Line(){}
    Line(Point _a,Point _b){a=_a;b=_b;}
}line[maxn];
 
bool cmp(Line u,Line v)
{
    return  u.a.x<v.a.x;
}
 
/**叉积--向量ca和向量cb求叉积*/
int cross(Point a,Point b,Point c)
{
    a.x-=c.x;a.y-=c.y;
    b.x-=c.x;b.y-=c.y;
    return a.x*b.y-a.y*b.x;
}
 
int main()
{
    int n,m,x1,y1,x2,y2;
    while(~scanf("%d",&n)&&n)
    {
        Clear(ans);
        Clear(num);
        scanf("%d%d%d%d%d",&m,&x1,&y1,&x2,&y2);
        for(int i=0;i<n;i++)
        {
            int Ui,Li;
            scanf("%d%d",&Ui,&Li);
            line[i]=Line(Point(Ui,y1),Point(Li,y2));
        }
        line[n] = Line(Point(x2,y1),Point(x2,y2));
        sort(line,line+n+1,cmp);
        Point s;
        while(m--)
        {
            scanf("%d%d",&s.x,&s.y);
            int l=0,r=n;
            while(l<=r)
            {
                int mid=(l+r)>>1;
                if(cross(line[mid].b,line[mid].a,s)>0)
                    r=mid-1;
                else l=mid+1;
            }
            ans[l]++;
        }
        for(int i=0;i<=n;i++)
            if(ans[i]) num[ans[i]]++;
        printf("Box\n");
        for(int i=1;i<=n;i++)
            if(num[i]) printf("%d: %d\n",i,num[i]);
    }
    return 0;
}