poj2398叉积之点定位+二分
问题说白了就是：看给定的点在哪两个线段之间。根据题目的描述，给定的点要么在两线段中间，要么左边，要么右边，所以需做一个叉积，来判定点与两条线段的位置关系（具体如下面的FindBelongBinIndex()函数描述）。
因为线段是排好序的了，所以可以二分查找。
#include <iostream>#include <algorithm>using namespace std;struct Point2D{Point2D(){x=0.0f;y=0.0f;}Point2D(double tx,double ty){x=tx;y=ty;}double x,y;};//Return the crossproduct of vec1*vec2double CrossProduct(Point2D vec1,Point2D vec2){return vec1.x*vec2.y-vec1.y*vec2.x;}//Comparision Functionbool IntLessComparision(int a,int b){return a<b;}bool PointXComparision(Point2D a,Point2D b){return a.x<=b.x;}//Find the index of the bin which the toy belongs to.inline int FindBelongBinIndex(Point2D upPos[],Point2D lowPos[],Point2D toyPos, int nBin ){int low=0,high=nBin-1;while(low<=high){int mid=(low+high)/2;//test midth bindouble crossLeft=CrossProduct( Point2D(lowPos[mid].x-upPos[mid].x,lowPos[mid].y-upPos[mid].y), Point2D(toyPos.x-upPos[mid].x,toyPos.y-upPos[mid].y));double crossRight=CrossProduct( Point2D(lowPos[mid+1].x-upPos[mid+1].x,lowPos[mid+1].y-upPos[mid+1].y), Point2D(toyPos.x-upPos[mid+1].x,toyPos.y-upPos[mid+1].y));if(crossLeft>0 && crossRight<0){return mid;}else if(crossLeft<0){high=mid-1;continue;}else if(crossRight>0){low=mid+1;continue;}}return -1;}int main(){int nCardboardNumber;int nBinNumber;int nToyNumber;//Store the i cardboard's up x value and low x value.Point2D upPos[5005];Point2D lowPos[5005];//The up and low y value of toy box. double lowY;double upY;//The toy number of each binint ToyNumberOfBin[5005];//The positions of toysPoint2D toyPosition[5005];scanf("%d",&nCardboardNumber);while(nCardboardNumber!=0){memset(ToyNumberOfBin,0,sizeof(ToyNumberOfBin) );nCardboardNumber+=2;//With the first and last cardboardnBinNumber=nCardboardNumber-1;//The number of the binscanf("%d",&nToyNumber);scanf("%lf%lf%lf%lf",&upPos[0].x,&upPos[0].y,&lowPos[nCardboardNumber-1].x,&lowPos[nCardboardNumber-1].y);lowPos[0].x=upPos[0].x;lowPos[0].y=lowPos[nCardboardNumber-1].y;upPos[nCardboardNumber-1].x=lowPos[nCardboardNumber-1].x;upPos[nCardboardNumber-1].y=upPos[0].y;for(int i=1;i<nCardboardNumber-1;i++){scanf("%lf%lf",&upPos[i].x,&lowPos[i].x);upPos[i].y=upPos[i-1].y;lowPos[i].y=lowPos[i-1].y;}sort(upPos,upPos+nCardboardNumber,PointXComparision);sort(lowPos,lowPos+nCardboardNumber,PointXComparision );for(int i=0;i<nToyNumber;i++){scanf("%lf%lf",&toyPosition[i].x,&toyPosition[i].y);int index=FindBelongBinIndex(upPos,lowPos,toyPosition[i],nBinNumber);if(index==-1){break;printf("Bounding Error/n");}else ToyNumberOfBin[index]++;}sort(ToyNumberOfBin,ToyNumberOfBin+nBinNumber,IntLessComparision);printf("Box\n");int k=0;while(ToyNumberOfBin[k]==0)k++;int tCount=1;while(k<nBinNumber){if(k<nBinNumber-1 && ToyNumberOfBin[k]==ToyNumberOfBin[k+1]){tCount++;}else{printf("%d: %d\n",ToyNumberOfBin[k],tCount);tCount=1;}k++;}scanf("%d",&nCardboardNumber);}return 0;}