#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; }