今天开始学习计算几何，百度了两篇文章，与君共勉！
题意：有一个盒子，被n块木板分成n+1个区域，每个木板从左到右出现，并且不交叉。 有m个玩具（可以看成点）放在这个盒子里，问每个区域分别有多少个玩具。
思路：首先，用叉积判断玩具是否在木板的左边，再用二分找到符合的最右边的木板，该木板答案加一。
#include<stdio.h>
#include<string.h>
struct point{
int x,y;
point(){}
point(int x_,int y_){
x=x_,y=y_;
}
point operator -(const point &b)const{
return point(x-b.x,y-b.y);
}
int operator *(const point &b)const{//点积
return x*b.x+y*b.y;
}
int operator ^(const point &b)const{//叉积
return x*b.y-y*b.x;
}
};
int cal(point p0,point p1,point p2){//小于0表示在p1处左折，大于0右折，等于0同线
return (p1-p0)^(p2-p0);
}
const int N=;
point s[N],e[N];
int ans[N];
int main(){
int n,m,x1,x2,y1,y2;
int x3,x4,i,f=;
while(~scanf("%d",&n)&&n){
scanf("%d%d%d%d%d",&m,&x1,&y1,&x2,&y2);
if(!f) f=;
else puts("");
memset(ans,,sizeof(ans));
for(i=;i<n;i++){
scanf("%d%d",&x3,&x4);
s[i]=point(x3,y1);
e[i]=point(x4,y2);
}
s[n]=point(x2,y1);
e[n]=point(x2,y2);
while(m--){
int l=,r=n,mid,x,y,tmp;
scanf("%d%d",&x,&y);
point p=point(x,y);
while(l<=r){
mid=(l+r)>>;
if(cal(p,s[mid],e[mid])<){
tmp=mid;
r=mid-;
}
else
l=mid+;
}
ans[tmp]++;
}
for(i=;i<=n;i++){
printf("%d: %d\n",i,ans[i]);
}
}
return ;
}