poj2318——TOYS

题意：求图中各个区域中有多少个玩具。

思路：外积+二分

ps:这小家伙确实淘气 只知当时头挺晕的...撑着将此题过了。休息

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
class T
{
public:
	int x1,x2;
};
T toy[5005];
int g[5005];
int y1,y2,n,m,x,y,t;
int f(int x1,int x2)
 {
	int f1=(toy[x1].x2-x)*(y1-y)-(y2-y)*(toy[x1].x1-x);
	int f2=(toy[x2].x2-x)*(y1-y)-(y2-y)*(toy[x2].x1-x);
	if(f1<0&&f2>0) return 0;
	else if(f1>0) return -1;//直线左
	else return 1;//直线右
}
void solve(int left,int right)
              {
	int mid=(left+right)/2;
	int k=f(mid,mid+1);
	if(k==0) {t=mid;return ;}
	else if(k<0)  solve(left,mid);
	else solve(mid+1,right);
}
int main()
{
	while(1)
	{
		int i;
		cin>>n;
		if(n==0) break;
		cin>>m>>toy[0].x1>>y1>>toy[n+1].x2>>y2;
		toy[0].x2=toy[0].x1;toy[n+1].x1=toy[n+1].x2;
		for(i=1;i<=n;i++)
			cin>>toy[i].x1>>toy[i].x2;
		memset(g,0,sizeof(g));
		for(i=0;i<m;i++)
		{
			cin>>x>>y;
			solve(0,n+1);
			g[t]+=1;
		}
		for(i=0;i<=n;i++)
		{
			printf("%d: %d\n",i,g[i]);
		}
		printf("\n");
	}
	return 0;
}