POJ2318-TOYS（判断点与线的位置关系）

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

The input file contains one or more problems. The first line of a problem consists of six integers, n m x1 y1 x2 y2. The number of cardboard partitions is n (0 < n <= 5000) and the number of toys is m (0 < m <= 5000). The coordinates of the upper-left corner and the lower-right corner of the box are (x1,y1) and (x2,y2), respectively. The following n lines contain two integers per line, Ui Li, indicating that the ends of the i-th cardboard partition is at the coordinates (Ui,y1) and (Li,y2). You may assume that the cardboard partitions do not intersect each other and that they are specified in sorted order from left to right. The next m lines contain two integers per line, Xj Yj specifying where the j-th toy has landed in the box. The order of the toy locations is random. You may assume that no toy will land exactly on a cardboard partition or outside the boundary of the box. The input is terminated by a line consisting of a single 0.

Output

The output for each problem will be one line for each separate bin in the toy box. For each bin, print its bin number, followed by a colon and one space, followed by the number of toys thrown into that bin. Bins are numbered from 0 (the leftmost bin) to n (the rightmost bin). Separate the output of different problems by a single blank line.

Sample Input

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

Sample Output

0: 2
1: 1
2: 1
3: 1
4: 0
5: 1

0: 2
1: 2
2: 2
3: 2
4: 2

Hint

As the example illustrates, toys that fall on the boundary of the box are "in" the box

解题思路，听说用二分做，但是我还没学。于是我还是想到了暴力循环，哈哈哈哈哈哈，无脑for就过了。开个玩笑，当然要想一下的。n条线可以把矩形分成n+1块区域，那么我们可以对所有的区域进行扫描，每扫描一块区域，对所有的玩具进行判定，符合条件的玩具记录下来。为了处理方便，我把第一块区域和最后一块区域分开了。那么怎么判断玩具是否符合条件呢？以第一块区域为例，如果玩具和线的向量差<=0，那么玩具肯定在线的右侧，对第一块区域而言，在线右侧的肯定符合条件呀（符合条件就是玩具丢进了第一个区域内）。同理，中间区域只需玩具和前一条线的向量差>0，并且玩具和当前这条线的向量差<=0就满足条件了。最后一块区域自己推一下吧，emmm。

等下次学了二分再试试，以后可能会陆续更新。

AC代码如下：

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<map>
#include<vector>
#include<cstring>
#include<string>
#include<set>
#include<stack>
#include<iostream>
using namespace std;
struct node
{
	int x;
	int y;
	node(int x=0,int y=0):x(x),y(y){}	//继承和初始成员变量 
}point[10005],toy[5005];

node operator - (node a,node b)		//重载 
{
	return node(a.x-b.x,a.y-b.y);
}

int det(node a,node b)
{
	return a.x*b.y-a.y*b.x;
}

int main()
{
	int n,m,x1,x2,y1,y2;
	int i,j;
	int cnt[5005];	//记录每块区域包含玩具的个数 
	while(scanf("%d",&n)&&n)
	{
		scanf("%d%d%d%d%d",&m,&x1,&y1,&x2,&y2);
		memset(cnt,0,sizeof(cnt));
		for(i=0;i<2*n-1;i+=2)
		{
			scanf("%d%d",&point[i].x,&point[i+1].x);
			point[i].y=y1;
			point[i+1].y=y2;
		}
		for(i=0;i<m;i++)
		{
			scanf("%d%d",&toy[i].x,&toy[i].y);
		}
		for(i=0;i<2*n;i+=2)	//从第一条线的的左上至最后一条线的左上。对于每块区域 ，查找所有满足条件的点并记录下来.每条直线扫描一次，跳过对每条直线的右下的扫描 
		{	
		
			if(i==0)	//扫描第一条线左上点时 
			{
				for(j=0;j<m;j++)
				{
					if(det(point[i+1]-point[i],toy[j]-point[i])<0)	cnt[i/2]++;	//当扫描到的玩具在线的右侧时，说明玩具在第一块区域，玩具数+1。 
				}
			}
			if(i>0)
			{
				for(j=0;j<m;j++)	//扫描中间n-1个区域所包含的点 
				{
					if(det(point[i+1]-point[i],toy[j]-point[i])<0&&det(point[i-1]-point[i-2],toy[j]-point[i-2])>0)	cnt[i/2]++;	
				}
			}
			if(i==2*n-2)	//扫描最后一条线左上点时 
			{
				for(j=0;j<m;j++)
				{
					if(det(point[i+1]-point[i],toy[j]-point[i])>0)	cnt[i/2+1]++;
				}
			}
		}
		for(i=0;i<n+1;i++)
		{
			printf("%d: %d\n",i,cnt[i]);
		}
		printf("\n");
	}
	return 0;
}