链接：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\n",j,s[j]);
printf("\n");
}
return 0;
}
id=2398">链接：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\n");
for(i=1;i<=n;i++)
if(a[i])
printf("%d: %d\n",i,a[i]);
}
return 0;
}