叉积判两向量顺逆时针——poj2318

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
using namespace std;
#define db double

const db EPS = 1e-9;
inline int sign(db a){return a<-EPS?-1:a>EPS;}
inline int cmp(db a,db b){return sign(a-b);}

struct P {
    db x,y;
    P(){}
    P(db _x,db _y):x(_x),y(_y){}
    P operator+(P p){return P(x+p.x, y+p.y);}
    P operator-(P p){return P(x-p.x, y-p.y);}
    P operator*(db d){return P(x*d, y*d);}
    P operator/(db d){return P(x/d, y/d);}
    bool operator<(P p)const {//先左再下 
        int c=cmp(x, p.x);
        if(c)return c==-1;
        return cmp(y, p.y)==-1;
    }
    bool operator==(P o)const {
        return cmp(x,o.x)==0 && cmp(y,o.y)==0; 
    }
    
    db dot(P p){return x*p.x+y*p.y;}
    db det(P p){return x*p.y-y*p.x;}
}; 
db cross(P p1,P p2,P p3){return (p2.x-p1.x)*(p3.y-p1.y)-(p3.x-p1.x)*(p2.y-p1.y);}//向量(p1,p2)^(p1,p3) 
int crossOp(P p1,P p2,P p3){return sign(cross(p1,p2,p3));}//(p1,p2)^(p1,p3)，1：p3在p2逆时针 

int n,m,cnt[5005];
double x1,y1,x2,y2;
pair<P,P>lines[5005];

int main(){
    while(scanf("%d",&n) && n!=0){
        memset(cnt,0,sizeof cnt);
        scanf("%d",&m);
        scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
        pair<P,P>l = make_pair(P(x1,y2),P(x1,y1));
        pair<P,P>r = make_pair(P(x2,y2),P(x2,y1));
        lines[0]=l;lines[n+1]=r;
        
        for(int i=1;i<=n;i++){
            double U,L;
            scanf("%lf%lf",&U,&L);
            pair<P,P>line=make_pair(P(L,y2),P(U,y1));
            lines[i]=line;
        }
        while(m--){
            P p;
            scanf("%lf%lf",&p.x,&p.y);
            int flag=0;
            for(int i=1;i<=n;i++){ 
                P low=lines[i].first;
                P up=lines[i].second;
                if(crossOp(low,p,up)<0){
                    flag=1;cnt[i]++;break;
                } 
            }
            if(flag==0)cnt[n+1]++;
        }
        for(int i=1;i<=n+1;i++)
            cout<<i-1<<": "<<cnt[i]<<'
';
        puts("");
    }
}