POJ 2318 TOYS

[計算幾何]
寫計算幾何耍廢XDD

#include<cstring>
#include<stdio.h>
#include<algorithm>
int top,bottom;
class line
{
public:
    int U,L;
    line(){U=0;L=0;}
    void set(int _u,int _l){U=_u;L=_l;}
};
class point
{
public:
    int X,Y;
    point(){X=0;Y=0;}
};
bool operator<(line L1,line L2)
{
    return L1.U<L2.U;
}
bool operator<(line L,point P)
{
    return (((P.Y-bottom)*(L.U-L.L)+(L.L-P.X)*(top-bottom))<0);
}
bool operator<(point P,line L)
{
    return (1-(L<P));
}
line    Ls[5000];   int Lcnt;
int Pcnt;
int Boxcnt[5001];
int main()
{
    while(scanf("%d",&Lcnt)==1)
    {
        if(Lcnt==0) break;
        scanf("%d",&Pcnt);
        memset(Boxcnt,0,sizeof(Boxcnt));
        Lcnt+=2;
        int x1,x2;scanf("%d %d %d %d",&x1,&top,&x2,&bottom);
        Ls[0].set(x1,x1);
        Ls[Lcnt-1].set(x2,x2);
        for(int lx=1;lx<Lcnt-1;lx++)
        {
            scanf("%d %d",&x1,&x2);
            Ls[lx].set(x1,x2);
        }
        std::sort(Ls,Ls+Lcnt);
        point PP;
        for(int lx=0;lx<Pcnt;lx++)
        {
            scanf("%d %d",&PP.X,&PP.Y);
            for(int ly=0;ly<Lcnt-1;ly++)
            {
                if((Ls[ly]<PP)&&(PP<Ls[ly+1]))
                {
                    Boxcnt[ly]++;
                    break;
                }
            }
        }
        for(int ly=0;ly<Lcnt-1;ly++)
            printf("%d: %d\n",ly,Boxcnt[ly]);
        printf("\n");
    }
    return 0;
}