1 // 题意：问你每个区域有多少个点 2 // 思路：数据小可以直接暴力 3 // 也可以二分区间 4  5 #include <cstdio> 6 #include <cstring> 7 #include <iostream> 8 #include <algorithm> 9 #include <map>10 #include <set>11 #include <queue>12 #include <stdlib.h>13 #include <cmath>14 using namespace std;15 typedef long long LL;16 const LL inf = 1e18;17 const int N = 5000;18 19 struct Point{20     int x,y;21     Point(){}22     Point(int _x,int _y){23         x=_x;y=_y;24     }25     Point operator -(const Point &b)const{26         return Point(x-b.x,y-b.y);27     }28     int operator *(const Point &b)const{29         return x*b.x+y*b.y;30     }31     int operator ^(const Point &b)const{32         return x*b.y-y*b.x;33     } 34 };35 36 struct Line{37     Point s,e;38     Line(){}39     Line(Point _s,Point _e){40         s=_s,e=_e;41     }42 };43 44 int xmult(Point p0,Point p1,Point p2){45     return (p1-p0)^(p2-p0);46 }47 48 Line line[N];49 int ans[N];50 int main(){51     int n,m,x1,y1,x2,y2;52     bool first = true;53     while(~scanf("%d",&n)&&n){54         if(first) first=false;55         else printf("\n");56         scanf("%d%d%d%d%d",&m,&x1,&y1,&x2,&y2);57         for(int i=0;i<n;i++){58             int x,y;59             scanf("%d%d",&x,&y);60             line[i]=Line(Point(x,y1),Point(y,y2));61         }62         line[n]=Line(Point(x2,y1),Point(x2,y2));63         int x,y;64         Point p;65         memset(ans,0,sizeof(ans));66         int tem;67         while(m--){68             scanf("%d%d",&x,&y);69             p = Point(x,y);70             int l=0,r=n,mid;71             while(l<=r){72                 mid=(l+r)>>1;73                 if(xmult(p,line[mid].s,line[mid].e)<0){74                     tem=mid;75                     r=mid-1;76                 }77                 else l=mid+1;78             }79             ans[tem]++;80         }81         for(int i=0;i<=n;i++) printf("%d: %d\n",i,ans[i]);82     }83     return 0;84 }