Description

Calculate the number of toys that land in each bin of a partitioned toy box.
Mom and dad have a problem - their child John never puts his toys away when he is finished playing with them. They gave John a rectangular box to put his toys in, but John is rebellious and obeys his parents by simply throwing his toys into the box. All the toys get mixed up, and it is impossible for John to find his favorite toys.

John‘s parents came up with the following idea. They put cardboard partitions into the box. Even if John keeps throwing his toys into the box, at least toys that get thrown into different bins stay separated. The following diagram shows a top view of an example toy box.

For this problem, you are asked to determine how many toys fall into each partition as John throws them into the toy box.

Input

Output

Sample Input

5 6 0 10 60 03 14 36 810 1015 301 52 12 85 540 107 94 10 0 10 100 020 2040 4060 6080 80 5 1015 1025 1035 1045 1055 1065 1075 1085 1095 100

Sample Output

0: 21: 12: 13: 14: 05: 10: 21: 22: 23: 24: 2

Hint

Source

题意：

Mom和Dad有一个问题---他们的孩子John在玩后从不收捡他的玩具。他们给了John一个矩形箱子来放玩具，但John很不满，但又只好遵从父母之命，所以他只是简单地把玩具扔到玩具箱。结果所有的玩具都混到一起了，John不可能找到他最喜欢的玩具了。
John的父母想到了一个主意：他们把纸板箱分隔成盒子，即使John仍是扔玩具，至少那些扔到不同盒子中的玩具是隔开的。下图显示了一个玩具盒的俯视图：

对这个问题，要求你确定在John扔玩具时有多少玩具落进每个盒子里。计算在不同玩具箱中的玩具数。

输入

输入文件包含多个问题。每个问题的第一行是6个整数：n m x1 y1 x2 y2,n是纸板箱的分隔数(1≤n ≤ 5000)，m是玩具数(1≤ m ≤ 5000)，盒子的左上角与右下角的坐标分别由(x1,y1)与(x2,y2)表示。下面的n行中，每行有两个整数Ui Li,表示第i个盒子的隔板的坐标分别为(Ui,y1)与(Li,y2)。你可以假设这些由纸板箱隔开的盒子其隔板不会互相相交，而且它们是按从左到右的顺序依次给出的。接下来的m行中，每行的两个整数Xj， Yj分别表示第j个玩具落到的位置的坐标。玩具落下的位置是随机的。你可假设不会有玩具恰好落在隔板上也不会落到盒子外。输入以一个0结束。

输出

对每个测试用例，输出每个盒子中的玩具数，每个盒子一行，格式是，盒子编号：（一个空格）盒子中的玩具数。盒子编号从0开始（最左端的盒子）到n(最右端的盒子)。每两个测试用例之间输出一空行分隔。

用到了叉积这个知识，

判断A 点  是否在线段BC 左侧

只要 ABXAC>0即可；

#include<iostream>#include<cstdio>#include<cmath>#include<cstring>using namespace std;int n,m,x,y,ans[5100];int y11,y22;struct node{    int x1,x2;}p[5100];bool OK(int a)//叉积{    int xx1=p[a].x1-x,yy1=y11-y;    int xx2=p[a].x2-x,yy2=y22-y;    return xx2*yy1-yy2*xx1>0;}void work(){    int i;    for( i=1;i<=n;i++)//枚举可以过  所以没二分    {        if(OK(i))//是否在第i个隔板前面左边为true         break;    }    //一定在盒子内所以前面不满足就是最后一隔加1    ans[i-1]++;//因为是i的左边所以就i-1隔加1}int main(){    while(scanf("%d",&n))    {        if(n==0)break;        memset(ans,0,sizeof ans);        scanf("%d%d%d%d%d",&m,&p[0].x1,&y11,&p[n+1].x1,&y22);        p[0].x2=p[0].x1;        p[n+1].x2=p[n+1].x1;        int i,j;        for(i=1;i<=n;i++)        {            scanf("%d%d",&p[i].x1,&p[i].x2);        }        while(m--)        {            scanf("%d%d",&x,&y);            work();        }        for(i=0;i<=n;i++)        {            printf("%d: %d\n",i,ans[i]);        }        printf("\n");    }    return 0;}

POJ2318TOYS