（POJ 2318）TOYS 向量叉积

题目链接：http://poj.org/problem?id=2318

#include<stdio.h>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<queue>

#include <stack>

using namespace std;

#define ll long long

#define INF 0x3f3f3f3f

#define met(a,b) memset(a,b,sizeof(a))

#define N 5010

struct point

{

    int x,y;

}a;

struct lint

{

    point a,b;

}s[N];

int ans[N];

int pan(point a,point p,point p1)

{

    return (a.x - p1.x)*(p.y - p1.y)-(p.x-p1.x)*(a.y-p1.y);

    ///判断点a在点p与点p1连线的哪边，利用向量的叉积  p相对啊左转为正

}

void erfen(point a,int n)

{

    int l=,r=n-;

    while(l<r)

    {

        int mid=(l+r)/;

        if(pan(a,s[mid].a,s[mid].b)>)

            l=mid+;

        else

            r=mid;

    }

    if(pan(a,s[l].a,s[l].b)<)

        ans[l]++;

    else

    ans[l+]++;

}

int main()

{

    int n,m,x1,y1,x2,y2;

    int u1,l1;

    while(scanf("%d",&n),n)///以0为结束标志

    {

        scanf("%d %d %d %d %d",&m,&x1,&y1,&x2,&y2);

        met(ans,);

        for(int i=;i<n;i++)

        {

            scanf("%d %d",&u1,&l1);

            s[i].a.x=u1;

            s[i].a.y=y1;

            s[i].b.x=l1;

            s[i].b.y=y2;

        }

        for(int i=;i<m;i++)

        {

            scanf("%d %d",&a.x,&a.y);

            erfen(a,n);

        }

        for(int i=;i<=n;i++)

        {

            printf("%d: %d\n",i,ans[i]);

        }

        puts("");

    }

    return ;

}