poj 2318 判断点在多边形内

链接：http://poj.org/problem?id=2398

题意：有n个隔板，形成n+1个格子，求每个格子中的玩具数。

思路:对于每个玩具，二分求它在哪个格子。用叉积判断点是在直线的左边还是右边。

#include<iostream>
//#include<cmath>
#include<cstdio>
#include<cstring>
using namespace std;

const int maxn=5000+5;
int n,m,x1,y1,x2,y2;

struct Line
{
    int upp,low;
}line[maxn];

int toy[maxn];

int isleft(int x,int y,Line l)
{
    if(x<l.low+(y-y2)*(l.upp-l.low)*1.0/(y1-y2))
       return true;
    return false;
}

int binarysearch(int x,int y)//下标的对应
{
    int l=0,r=n,mid;
    while(l<r)
    {
        mid=l+(r-l)/2;
        if(isleft(x,y,line[mid]))
           r=mid;
        else l=mid+1;
    }
    return l;
}

int main()
{
    while(scanf("%d",&n) && n)
    {
        scanf("%d%d%d%d%d",&m,&x1,&y1,&x2,&y2);
        memset(toy,0,sizeof(toy));
        for(int i=0;i<n;++i)
            scanf("%d%d",&line[i].upp,&line[i].low);
        for(int i=0;i<m;++i)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            toy[binarysearch(x,y)]++;
        }
        for(int i=0;i<=n;++i)
            printf("%d: %d\n",i,toy[i]);
        printf("\n");
    }
    return 0;
}