学步园

题目大意：有一个盒子，n块挡板把盒子分成n+1部分,有m个玩具给出坐标，判断盒子中每个部分各有多少个玩具。

我的思路：直接枚举每个玩具在各个区域的情况，利用叉积判断，若叉积大于0则在该侧。（也可以用二分优化）

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define eps 1e-10

int dcmp(double x)
{
    if(fabs(x)<eps)//x==0
       return 0;
    else
       return x<0?-1:1;
}

struct point
{
    int x,y;
};
struct point dot[5000+10];//每个挡板的向量
struct point play[5000+10];//玩具的向量

double cross(double x1,double y1,double x2,double y2)//叉积
{
    return x1*y2-x2*y1;
}

int main()
{
    int n,m,i,j,k;
    int a[5000+10],b[5000+10];//挡板坐标
    int x1,y1,x2,y2;//盒子坐标
    int xx,yy;//玩具坐标
    while(scanf("%d%d",&n,&m)&&n!=0)//n个挡板,m个玩具
    {
        double temp;
        int ans[5000+10]={0};//最后结果
        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);//盒子坐标
        for(i=1;i<=n;i++)
        {
            scanf("%d%d",&a[i],&b[i]);
            dot[i].x=a[i]-b[i],dot[i].y=y1-y2;//挡板向量
        }
        int sum=0;
        for(i=1;i<=m;i++)
        {
            scanf("%d%d",&xx,&yy);//每个玩具的坐标
            for(j=1;j<=n;j++)//第几个挡板
            {
                play[i].x=xx-b[j],play[i].y=yy-y2;//玩具向量
                temp=cross(play[i].x,play[i].y,dot[j].x,dot[j].y);
                if(dcmp(temp)==-1)
                {
                    ans[j-1]++;
                    sum++;
                    break;
                }
            }
        }
        ans[n]=m-sum;
        for(i=0;i<=n;i++)
        printf("%d: %d\n",i,ans[i]);
        printf("\n");//注意格式
    }
    return 0;
}