Toy Storage

题目链接：https://vjudge.net/problem/POJ-2398#author=Jawen

题意：是TOYS的升级版，但也不难，在一个盒子里放入n块纸板进行分割，所有纸板不相交，但纸板的顺序是随机给的，已知m个玩具的坐标，问有多少个区间的玩具为i(1<=i<=n)。

思路：和TOYS题的思路一样，只需要在TOYS题的思路上加一个给纸板排序再用个数组桶排就可以了。

//#include <bits/stdc++.h>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iostream>
using namespace std;
typedef long long ll;
struct node
{
    int x,y,z;
}a[5005];
int book[5005],b[5005];
bool cmp(node s,node w)
{
    return s.z<w.z;
}
int fun(int x1,int y1,int x2,int y2)
{
    return x1*y2-y1*x2;
}
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        if(n==0)
            break;
        memset(book,0,sizeof(book));
        memset(b,0,sizeof(b));
        int m,x1,y1,x2,y2;
        cin>>m>>x1>>y1>>x2>>y2;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i].x>>a[i].y;
            a[i].z=min(a[i].x,a[i].y);
        }
        sort(a+1,a+n+1,cmp);
        for(int i=1;i<=m;i++)
        {
            int x,y;
            cin>>x>>y;
            int v=n;
            for(int j=1;j<=n;j++)
            {
                int s=a[j].y-a[j].x;
                int w=y2-y1;
                if(fun(s,w,x-a[j].x,y-y1)<0)
                {
                    v=j-1;
                    break;
                }
            }
            book[v]++;
        }
        for(int i=0;i<=n;i++)
          b[book[i]]++;
        cout<<"Box"<<endl;
        for(int i=1;i<=n;i++)
        {
            if(b[i]>0)
                printf("%d: %d
",i,b[i]);
        }
    }
}