题目大意：有一个矩形盒子，盒子里会有一些木块线段，并且这些线段是按照顺序给出的，有n条线段，把盒子分层了n+1个区域,然后有m个玩具，这m个玩具的坐标是已知的，问最后每个区域有多少个玩具
解题思路：因为线段是有序给出，所以不用排序，判断某个点在哪个区域，采用二分法，将某个点和线段的叉积来判断这个点是在线的左边或者右边，根据这个来二分找出区域
代码和思路参考与此链接：http://blog.csdn.net/wangjian8006
这也算我入门计算几何的第一道题了，首先看了一些有关资料，了解到叉积的重要性！！有2点，p1，p2构成一条线段L，L左边有一点p3，右边有一点p4，则（p1-p2）x（p3-p1）>0，（p1-p2）x（p4-p1）<0。
也就是说在L左边的点叉积>0，右边的<0。
剩下的就是二分找答案了，在记录到数组中，最后输出。
#include <iostream>
using namespace std;
#define _MAXL_ 5010 typedef struct{
int x, y;
}POINT; typedef struct{
POINT first,second;
}LINE; class CBox{
private:
int nTop,nLeft,nRight,nButtom;
int nCountLine; //记录盒子里有多少条线
LINE *pLine; //记录线的信息
int *pRange; //记录区间中的玩具有多少个
int Multi(POINT p1,POINT p2,POINT p0); //叉积计算
public:
CBox();
virtual ~CBox();
void SetBorder(int top,int left,int right,int buttom); //设置盒子矩形坐标
void AddLine(int first,int second); //在盒子中增加一条线
int GetRange(int val); //得到某个区间中的玩具个数
void SetToy(POINT toy); //在盒子里放一个玩具
}; CBox::CBox(){
nCountLine = 0;
pLine = new LINE[_MAXL_];
pRange = new int[_MAXL_];
memset(pRange,0,sizeof(pRange)*_MAXL_);
} CBox::~CBox(){
delete []pLine;
delete []pRange;
} void CBox::SetBorder(int top,int left,int right,int buttom){
nTop = top;
nLeft = left;
nRight = right;
nButtom = buttom;
} void CBox::AddLine(int topx,int buttomx){
pLine[nCountLine].first.x = topx;
pLine[nCountLine].first.y = nTop;
pLine[nCountLine].second.x = buttomx;
pLine[nCountLine].second.y = nButtom;
nCountLine++;
} int CBox::GetRange(int val){
return pRange[val];
} int CBox::Multi(POINT p1,POINT p2,POINT p0){
return (p1.x - p0.x) * (p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y);
} void CBox::SetToy(POINT toy){ //利用二分查找，查找出该点在哪个区间
int l, r, mid;
l=0,r=nCountLine-1;
while (l < r){
mid = (l+r)>>1;
if (Multi(toy, pLine[mid].first, pLine[mid].second) > 0) l = mid + 1;
else r = mid;
}
if (Multi(toy, pLine[l].first, pLine[l].second) < 0) pRange[l]++;
else pRange[l+1]++;
} int main(){
int i,fx,lx;
POINT a,b;
int n,m;
while(cin>>n && n){
cin>>m>>a.x>>a.y>>b.x>>b.y;
CBox box;
box.SetBorder(a.y,a.x,b.x,b.y);
for(i = 0;i < n;i++){
cin>>fx>>lx;
box.AddLine(fx,lx);
} for(i = 0;i < m;i++){
cin>>a.x>>a.y;
box.SetToy(a);
} for(i = 0;i <= n;i++){
cout<<i<<": "<<box.GetRange(i)<<endl;
}
cout<<endl;
}
return 0;
}