题目大意：
有一个矩形盒子，盒子里会有一些木块线段，并且这些线段是按照顺序给出的，有n条线段，把盒子分层了n+1个区域
然后有m个玩具，这m个玩具的坐标是已知的，问最后每个区域有多少个玩具
输入：
输入文件包含一个或多个问题。一个问题的第一行包含六个整数，N M x1 y1 x2 y2。纸板分区的数量是n（0＜n＝5000），玩具的数量是m（0＜＜5000）。左上角的坐标和框的右下角（x1，y1）是（x2，y2），并分别。以下N行，每行包含两个整数，Ui Li，表示第i个纸板分区的结束是在坐标（Ui，y1）和（Li，Y2）。您可以假设纸板分区彼此不相交，它们是从左到右按排序顺序指定的。接下来的m行每行包含两个整数，Xj Yj指定的第j个玩具已经降落在箱。玩具位置的顺序是随机的。你可以假设没有玩具会准确地落在硬纸板的隔板上或盒子的外面。输入由一个单0组成的行终止。
输出：
每个问题的输出将是玩具箱中每个独立的箱子的一行。对于每一个箱子，打印它的编号，后面是冒号和一个空格，后面跟着丢进bin的玩具数量。箱编号从0（最左边的桶）N（最右边的垃圾桶）。用一条空行分隔不同问题的输出。
样例：
输入：
5 6 0 10 60 0
3 1
4 3
6 8
10 10
15 30
1 5
2 1
2 8
5 5
40 10
7 9
4 10 0 10 100 0
20 20
40 40
60 60
80 80
5 10
15 10
25 10
35 10
45 10
55 10
65 10
75 10
85 10
95 10
0
输出：
0: 2
1: 1
2: 1
3: 1
4: 0
5: 1
0: 2
1: 2
2: 2
3: 2
4: 2
题解：叉积+二分
每读入一个玩具，用二分将其所在的位置找出，具体操作如下
1.叉积为负，玩具在当前位置的左边
2.叉积为正，玩具在右边
二分完后要特判：叉积大于0则位置要右移一位
1 #include<cstdio> 2 #include<algorithm> 3 #include<cstring> 4 #include<iostream> 5 using namespace std; 6 struct lin 7 { 8 int upx,downx,upy,downy; 9 }line[10001]; 10 int upy,upx,downx,downy,n,ans[10001],m; 11 void add_line(int x1,int x2,int i) 12 { 13 line[i].upx=x1; 14 line[i].upy=upy; 15 line[i].downx=x2; 16 line[i].downy=downy; 17 } 18 int chaji(int i,int x,int y) 19 { 20 int dx=x-line[i].downx,dy=y-line[i].downy; 21 int fx=line[i].upx-line[i].downx,fy=line[i].upy-line[i].downy; 22 return (dx*fy-dy*fx); 23 } 24 void set_toy(int x,int y) 25 {int l,r; 26 l=1;r=n; 27 while (l<r) 28 { 29 int mid=(l+r)/2; 30 if (chaji(mid,x,y)>0) l=mid+1; 31 else r=mid; 32 } 33 if (chaji(l,x,y)>=0) l++; 34 ans[l]++; 35 } 36 int main() 37 {int i,j,x1,x2,x,y; 38 while (cin>>n&&n) 39 { 40 memset(ans,0,sizeof(ans)); 41 cin>>m>>upx>>upy>>downx>>downy; 42 for (i=1;i<=n;i++) 43 { 44 scanf("%d%d",&x1,&x2); 45 add_line(x1,x2,i); 46 } 47 for (i=1;i<=m;i++) 48 { 49 scanf("%d%d",&x,&y); 50 set_toy(x,y); 51 } 52 for (i=1;i<=n+1;i++) 53 printf("%d: %d ",i-1,ans[i]); 54 cout<<endl; 55 } 56 }