题目：
http://poj.org/problem?id=2318题意：
给出一个箱子的宽和高，其中有一些隔板，给出这些板子在箱子上下边上的点的位置，给出一些玩具的位置坐标，玩具会被放在某两个隔板之间，隔板分割的区域为0~n，求最后每个区域有多少个玩具。
思路：
隔板是有序给的，只要用叉乘判断每个玩具在某个隔板的左边还是右边，然后二分找就行了。
铜牌狗又要开始重新刷题了。
代码：
#define N 112345
int n,m;
int f[N];
struct point
{
double x,y;
}a[N],b[N],t;
double cross3(point p0,point p1,point p2)
{
return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}
int main()
{
int i,j,k,T,cas;
double x,y,z,x1,x2,y1,y2;
cas=0;
while(scanf("%d%d%lf%lf%lf%lf",&n,&m,&x1,&y1,&x2,&y2)!=EOF&&n)
{
memset(f,0,sizeof(f));
for(i=0;i<n;i++)
{
scanf("%lf%lf",&a[i].x,&b[i].x);
a[i].y=y1;b[i].y=y2;
}
a[n].x=x2;a[n].y=y1;
b[n].x=x2;b[n].y=y2;
while(m--)
{
scanf("%lf%lf",&t.x,&t.y);
i=0;j=n;
while(i<j)
{
int mid=(i+j)>>1;
if(cross3(a[mid],b[mid],t)<=0) j=mid;
else i=mid+1;
}
f[i]++;
}
printf("%s",cas++?"\n":"");
for(i=0;i<=n;i++)
printf("%d: %d\n",i,f[i]);
}
return 0;
}
题目：
http://poj.org/problem?id=2398题意：
和2318基本一样，就是隔板未排序，并且输出的是有x个玩具的隔间有多少个。
思路：
加个排序和输出多扫一边就行了。代码：
#define N 112345
int n,m;
int flag,sum,ave,ans,res,len,ans1,ans2;
int f[N],ff[N];
struct point
{
double x,y,xx,yy;
friend bool operator < (point a,point b)
{
return a.x < b.x;
}
}a[N],t;
double cross3(point p0,point p2)
{
return (p0.xx-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p0.yy-p0.y);
}
int main()
{
int i,j,k,T,cas;
double x,y,z,x1,x2,y1,y2;
while(scanf("%d%d%lf%lf%lf%lf",&n,&m,&x1,&y1,&x2,&y2)!=EOF&&n)
{
memset(f,0,sizeof(f));
memset(ff,0,sizeof(ff));
for(i=0;i<n;i++)
{
scanf("%lf%lf",&a[i].x,&a[i].xx);
a[i].y=y1;a[i].yy=y2;
}
a[n].x=x2;a[n].y=y1;
a[n].xx=x2;a[n].yy=y2;
sort(a,a+n);
cas=m;
while(cas--)
{
scanf("%lf%lf",&t.x,&t.y);
i=0;j=n;
while(i<j)
{
int mid=(i+j)>>1;
if(cross3(a[mid],t)<=0) j=mid;
else i=mid+1;
}
f[i]++;
}
printf("Box\n");
for(i=0;i<=n;i++)
ff[f[i]]++;
for(i=1;i<=m;i++)
if(ff[i])
printf("%d: %d\n",i,ff[i]);
}
return 0;
}