poj2398,（模板）计算几何，用叉积判点在线左右

#include 
#include 
#include 
#include 
using namespace std;
struct Point{
    double x,y;
    Point(){
    };
    Point(double x,double y):x(x),y(y){
    };
    double operator ^(Point b){return x*b.y-y*b.x;//-,no+交叉相乘 
    }
    Point operator -(Point b){return Point(x-b.x,y-b.y);
    }
};
struct Line{
    Point a,b;
    Line(){
    };
    Line(Point a,Point b):a(a),b(b){
    };
};
int n,m,x1,y1,x2,y2,u,v,x,y;
const int N=1004;
int pos[N];//记录每个区间的玩具数 
Line line[N];//分割线 
int cnt[N];//记录i个玩具数的区间数有多少个 
const double EPS=1e-8;
int seg(double x){//防止double失精 
    if(fabs(x)<EPS) return 0;//记住加fabs 
    if(x>0) return 1;
    return -1;
}
bool check(double x,double y,int li){
    Point p(x,y);
    if(seg((line[li].a-p)^(line[li].b-p))<0)return true;//矢量是终-起，a上b下，小于0 顺时针，在mid线左 
    return false;
}
void search(double x,double y){
    int l=0,r=n-1,mid;
    while(l<=r){//区域按区间的右边排序从0~n
        mid=(l+r)/2;
        if(check(x,y,mid)) r=mid-1;
        else l=mid+1;
    }
    pos[l]++;//出循环时右边是r，右边是l
}
bool cmp(Line a,Line b){
    return a.a.x<b.a.x;
}
int main(int argc, char** argv) {
    ios::sync_with_stdio(false);
    while(cin>>n,n){
        cin>>m>>x1>>y1>>x2>>y2;//x1左，y1上，x2右，y2下 
        cout<<"Box"<<endl;
        memset(pos,0,sizeof(pos));
        memset(cnt,0,sizeof(cnt));//记住刷新 
        for(int i=0;i<n;i++){
            cin>>u>>v;
            line[i]=Line(Point(u,y1),Point(v,y2));//第一个a点是上点，b点是下点 
        }
        sort(line,line+n,cmp);//要排序；不然无法二分 
        for(int j=1;j<=m;j++){
            cin>>x>>y;
            search(x,y);
        }
        for(int i=0;i<=n;i++){//统计玩具数为pos[i]的区间数 
            if(pos[i]) cnt[pos[i]]++;
        }
        for(int i=1;i<=m;i++){//遍历玩具数找到答案 
            if(cnt[i]) cout<<i<<": "<<cnt[i]<<endl;
        }
    }
    return 0;
}