POJ 2398 判断点在多边形内外

题意：给出一个矩形，再给出n条两端点分别在上下边的线段，然后给出m个点，要求按每个区域内的点数的升序输出点数t，后面为区域内有t的区域数。

这题按照题意做注意要对矩形内的边排序然后再二分判断点在那个区域里。

#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct point
{
    double x,y;
};
struct edge
{
    point up,down;
};
double Direction(point a,point b,point c)
{
    return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
}
bool On_Segment(point pi,point pj,point pk)
{
    if(pk.x>=min(pi.x,pj.x)&&pk.x<=max(pi.x,pj.x)&&pk.y>=min(pi.y,pj.y)&&pk.y<=max(pi.y,pj.y))
        return 1;
    return 0;
}
bool Segment_Intersect(point p1,point p2,point p3,point p4)
{
    double d1=Direction(p3,p4,p1),d2=Direction(p3,p4,p2),d3=Direction(p1,p2,p3),d4=Direction(p1,p2,p4);
    if(((d1>0&&d2<0)||(d1<0&&d2>0))&&((d3>0&&d4<0)||(d3<0&&d4>0)))
        return 1;
    if(d1==0&&On_Segment(p3,p4,p1))
        return 1;
    if(d2==0&&On_Segment(p3,p4,p2))
        return 1;
    if(d3==0&&On_Segment(p1,p2,p3))
        return 1;
    if(d4==0&&On_Segment(p1,p2,p4))
        return 1;
    return 0;
}
int Pandingdian(point a,edge l,edge r)//1在多边形上 2在多边形外 0在多边形内
{
    point b,polygon[6];
    b.x=-9999999,b.y=a.y;
    int n=4,sum=0;
    polygon[0]=l.up,polygon[1]=l.down,polygon[2]=r.down,polygon[3]=r.up;
    polygon[n]=polygon[0];
    for(int i=1; i<=n; i++)
        if(polygon[i].y-polygon[i-1].y!=0&&Segment_Intersect(a,b,polygon[i],polygon[i-1]))
        {
            if(Direction(a,polygon[i],polygon[i-1])==0)
                return 1;
            sum++;
        }
    if(sum&1)
        return 0;
    return 2;
}
int cmp(edge a,edge b)
{
    return a.up.x<b.up.x;
}
int cmp2(int a,int b)
{
    return a>b;
}
point lt,rb,temp;
edge data[1005];
int main()
{
    int n,m,ans[1005],wans[1005];
    while(~scanf("%d",&n),n)
    {
        scanf("%d%lf%lf%lf%lf",&m,<.x,<.y,&rb.x,&rb.y);
        memset(ans,0,sizeof(ans));
        memset(wans,0,sizeof(wans));
        data[0].up=lt,data[0].down.x=lt.x,data[0].down.y=rb.y;
        point u,d;
        u.y=lt.y,d.y=rb.y;
        for(int i=1; i<=n; i++)
            scanf("%lf%lf",&u.x,&d.x),data[i].up=u,data[i].down=d;
        data[n+1].down=rb,data[n+1].up.y=lt.y,data[n+1].up.x=rb.x;
        sort(data,data+n+2,cmp);
        while(m--)
        {
            scanf("%lf%lf",&temp.x,&temp.y);
            int l=0,r=n+1,mid;
            while(l<r)
            {
                mid=(l+r)/2;
                int w=Pandingdian(temp,data[mid],data[r]);
                if(w==0||w==1)
                {
                    if(r-mid==1)
                    {
                        ans[mid]++;
                        break;
                    }
                    l=mid;
                }
                else if(mid-l==1)
                {
                    ans[l]++;
                    break;
                }
                else
                    r=mid;
            }
        }
        sort(ans,ans+n+1,cmp2);
        for(int i=0; i<n+1; i++)
        {
            if(ans[i]==0)
                break;
            wans[ans[i]]++;
        }
        puts("Box");
        for(int i=1; i<=ans[0]; i++)
            if(wans[i])
                printf("%d: %d\n",i,wans[i]);
    }
    return 0;
}