poj 2318 TOYS

 1 #include<cstdio>
 2 #include<cstring>
 3 #define N 1000005
 4 #define LL long long
 5 #define inf 0x3f3f3f3f
 6 using namespace std;
 7 inline int ra()
 8 {
 9     int x=0,f=1; char ch=getchar();
10     while (ch<‘0‘ || ch>‘9‘) {if (ch==‘-‘) f=-1; ch=getchar();}
11     while (ch>=‘0‘ && ch<=‘9‘) {x=x*10+ch-‘0‘; ch=getchar();}
12     return x*f;
13 }
14 int n,m,ans[5005];
15 struct point{int x,y;};
16 struct segment{point a,b;}s[5005];
17 point sub(point a, point b){
18     point t; t.x=a.x-b.x, t.y=a.y-b.y; return t;
19 }
20 int cross(point a, point b){
21     return a.x*b.y-b.x*a.y;
22 }
23 int turn(point p1, point p2, point p3){
24     return cross(sub(p2,p1),sub(p3,p1));
25 }
26 void search(point x)
27 {
28     int l=1,r=n,tmp=0;
29     while (l<=r)
30     {
31         int mid=l+r>>1;
32         if (turn(s[mid].a,s[mid].b,x)>=0) tmp=mid,l=mid+1;
33             else r=mid-1; 
34     }
35     ans[tmp]++;
36 }
37 int main()
38 {
39     while (scanf("%d",&n) && n)
40     {
41         memset(ans,0,sizeof(ans));
42         int x1,x2,y1,y2,t1,t2;
43         scanf("%d%d%d%d%d",&m,&x1,&y1,&x2,&y2);
44         for (int i=1; i<=n; i++)
45         {
46             scanf("%d%d",&t1,&t2);
47             s[i].a.x=t1; s[i].a.y=y1;
48             s[i].b.x=t2; s[i].b.y=y2;
49         }
50         for (int i=1; i<=m; i++)
51         {
52             point t;
53             scanf("%d%d",&t.x,&t.y);
54             search(t);
55         }
56         for (int i=0; i<=n; i++)
57             printf("%d: %d\n",i,ans[i]);
58         puts("");
59     }
60     return 0;
61 }