poj 2318 TOYS & poj 2398 Toy Storage (叉积)

链接：poj 2318

题意：有一个矩形盒子，盒子里有一些木块线段。而且这些线段坐标是依照顺序给出的。

有n条线段，把盒子分层了n+1个区域,然后有m个玩具。这m个玩具的坐标是已知的，问最后每一个区域有多少个玩具

分析：从左往右。直到推断玩具是否在线段的逆时针方向为止。这个就须要用到叉积，当然能够用二分查找优化。

叉积：已知向量a(x1,y1),向量b(x2,y2),axb=x1*y2-x2*y1,

若axb>0,a在b的逆时针方向，若axb<0,则a在b的顺时针方向

注：每组数据后要多空一行

#include<stdio.h>
#include<string.h>
int chaji(int x1,int y1,int x2,int y2)
{
    return x1*y2-x2*y1;               
}
int main()
{
    int u[5010],l[5010],x,y,x1,y1,x2,y2,m,n,i,j,s[5010];
    while(scanf("%d",&n)!=EOF){
        if(n==0)
            break;
        scanf("%d%d%d%d%d",&m,&x1,&y1,&x2,&y2);
        for(i=0;i<n;i++)
            scanf("%d%d",&u[i],&l[i]);
        u[n]=l[n]=x2;                 //将最后一个线段加上
        memset(s,0,sizeof(s));
        for(i=0;i<m;i++){
            scanf("%d%d",&x,&y);
            for(j=0;j<=n;j++)
                if(chaji(u[j]-l[j],y1-y2,x-l[j],y-y2)>0){      //叉积推断
                    s[j]++;
                    break;
                }
        }
        for(j=0;j<=n;j++)
            printf("%d: %d
",j,s[j]);
        printf("
");
    }
    return 0;
}

链接：poj 2398

意思与上题一样。仅仅只是给出的线段乱序的，所以须要排序，

输出也有点不同，须要输出有玩具1-m个的区间有多少个，按顺序输出

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct point
{
    int l,u;
}p[1010];
int chaji(int x1,int y1,int x2,int y2)
{
    return x1*y2-x2*y1;
}
int cmp(struct point a,struct point b)
{
    if(a.l!=b.l)
        return a.l<b.l;
    return a.u<b.u;
}
int main()
{
    int x,y,x1,y1,x2,y2,m,n,i,j,s[1010],a[1010];
    while(scanf("%d",&n)!=EOF){
        if(n==0)
            break;
        scanf("%d%d%d%d%d",&m,&x1,&y1,&x2,&y2);
        for(i=0;i<n;i++)
            scanf("%d%d",&p[i].u,&p[i].l);
        p[n].u=p[n].l=x2;
        sort(p,p+n+1,cmp);             //对线段排序
        memset(s,0,sizeof(s));
        memset(a,0,sizeof(a));
        for(i=0;i<m;i++){
            scanf("%d%d",&x,&y);
            for(j=0;j<=n;j++)
                if(chaji(p[j].u-p[j].l,y1-y2,x-p[j].l,y-y2)>0){
                    s[j]++;
                    break;
                }
        }
        for(j=0;j<=n;j++)
            a[s[j]]++;
        printf("Box
");
        for(i=1;i<=n;i++)
            if(a[i])
                printf("%d: %d
",i,a[i]);
    }
    return 0;
}