//和2318差不多，只是输入的board是无序的，输出是玩具数为t(>0)的箱子数(>0)
#include<iostream>
#include<stdlib.h>
using namespace std;
#define MAXN 5000+1
#define eps 1e-8
#define _sign(x) ((x)>eps?1:((x)<-eps?2:0))
struct point
{int x,y;};
struct line{point a,b;};
int ans[MAXN];
line board[MAXN];
double xmult(point p0,point p1,point p2){//叉积，囧
return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}
int cmp(const void *a,const void *b)
{
line *aa=(line*)a,*bb=(line*)b;
if(aa->a.x == bb->a.x)
return aa->b.x - bb->b.y;
else return aa->a.x - bb->a.x;
}
int main()
{
int n,m,x1,y1,x2,y2,u1,u2,i;
point toys;
while(scanf("%d",&n)!=EOF && n )
{
memset(ans,0,sizeof(ans));
scanf("%d%d%d%d%d",&m,&x1,&y1,&x2,&y2);
for(i=0;i<n;i++)
{
scanf("%d%d",&u1,&u2);
board[i].a.x=u1;
board[i].a.y=y1;
board[i].b.x=u2;
board[i].b.y=y2;
}
qsort(board,n,sizeof(board[0]),cmp);
board[n].a.x=x2;
board[n].a.y=y1;
board[n].b.x=x2;
board[n].b.y=y2;
for(i=0;i<m;i++)
{
scanf("%d%d",&(toys.x),&(toys.y));
int low=0,hig=n,mid;
while(low+1<hig)
{
mid=(low+hig)>>1;
double res=xmult(board[mid].a,board[mid].b,toys);
if(res>0) low=mid;
else hig=mid;
}
if(xmult(board[low].a,board[low].b,toys)<0) ans[low]++;
else ans[low+1]++;
}
printf("Box\n");
int t=1,c;
for(t=1;t<=m;t++)
{
for(i=0,c=0;i<=n;i++)
{
if(ans[i]==t)
{
c++;
ans[i]=0;
}
}
if(c>0)
printf("%d: %d\n",t,c);
m=m-c*t;
}
}
return 0;
}posted on 2009-10-04 13:12
wyiu 阅读(198)
评论(0) 编辑 收藏 引用 所属分类:
POJ