BUPT 2017 summer training (16) #2 A
有一个玩具盒,被n个隔板分开成左到u右n+1个区域,然后给每个玩具的坐标,求每个区域有几个玩具。
依次用叉积判断玩具在每个隔板左边还是右边。
#include <cstdio>
#define N 50001
int n,m;
int x1,y1,x2,y2,u[N],l[N];
int ans[N];
int xmul(int x1,int y1,int x2,int y2){
return (x1*y2)-(x2*y1);
}
int main(){
while(scanf("%d",&n),n){
scanf("%d%d%d%d%d",&m,&x1,&y1,&x2,&y2);
for(int i=0;i<n;++i)
scanf("%d%d",u+i,l+i),ans[i]=0;
ans[n]=0;
for(int i=0,j,x,y;i<m;++i){
scanf("%d%d",&x,&y);
for(j=0;j<n;++j)
if(xmul(x-l[j],y-y2,u[j]-l[j],y1-y2)<=0)
break;
++ans[j];
}
for(int i=0;i<=n;++i)
printf("%d: %d\n",i,ans[i]);
puts("");
}
}