题目连接： http://poj.org/problem?id=2318 http://poj.org/problem?id=2398
两题类似的题目，2398是2318的升级版。
题目大概是说，有一个矩形的柜子，中间有一些隔板。告诉你每个隔板的坐标，还有一些玩具的坐标，统计玩具在哪个格子里。
这题的思路很简单，如果玩具在某个隔板的左边和右边叉乘的正负是不同的。如图：
图中点P在线段CD的左边，则向量PC和向量PD叉乘结果小于0。反之P在AB的左边，向量PA叉乘PB大于0。
因此利用这个性质以及排序好的线段列表，通过二分思想，可以快速知道点在哪个格子内。
代码：
#include<stdio.h>
#include<math.h>
#define PI 3.14159265358979323846
#define MAX(x,y) ((x)>(y)?(x):(y))
#define MIN(x,y) ((x)<(y)?(x):(y))
#define ABS(x) (((x)>0)?(x):(-(x)))
#define SIGN(x) (((x)<0)?-1:1)
#define EPS 0.000001/*精度控制*/
#define N 5005
/*坐标的定义*/
typedef double coo;/*int*/
/*点、向量*/
typedef struct POINT
{
coo x,y;
}point,vector;
/*线段*/
typedef struct SEGMENT
{
point p1,p2;/*p[2];*/
}segment;
/*判相等*/
int is_equel(double a,double b)
{
double c=ABS(a-b);
if(c<=EPS) return ;/*相等*/
else return ;/*不相等*/
}
/*向量的减法p1-p2*/
vector vector_minus(vector p1,vector p2)
{
vector p;
p.x=p1.x-p2.x;
p.y=p1.y-p2.y;
return p;
}
/*向量叉乘*/
double cross_product(vector p1,vector p2)
{/*x1y2-x2y1*/
return p1.x*p2.y-p1.y*p2.x;
}
int bijiao(segment s1,segment s2)/*比较两个线段的位置< */
{
if(s1.p1.x<s2.p1.x) return ;
if(s1.p1.x==s2.p1.x&&s1.p2.x<s2.p2.x) return ;
return ;
}
int Partition(segment r[],int low,int high)/*升序*/
/*返回支点最终位置*/
{
segment x;/*类型具体*/
if(low>high) return ;
if(low==high) return low;
x=r[low];
while(low<high)
{
while(low<high&&bijiao(x,r[high])) high--; /*<*/
if(low<high){r[low]=r[high];low++;}
while(low<high&&bijiao(r[low],x)) low++; /*>*/
if(low<high){r[high]=r[low];high--;}
}
r[low]=x;
return low;
}
void Quick_sort(segment r[],int m,int n) /*排序从r[m]到r[n]*/
{
int i;
if(m>=n) return;
i=Partition(r,m,n);
Quick_sort(r,m,i-);
Quick_sort(r,i+,n);
} int BinSearch(segment a[],int n,point k)/*在有序的数组a[0]~a[n-1]中查找k元素*/
{
int low=,high=n-,mid;
while(low<=high)
{
mid=low+((high-low)/);
if(cross_product(vector_minus(a[mid].p1,k),vector_minus(a[mid].p2,k))<) high=mid-;/*线段在右边*/
else low=mid+;
}
if(low>high) return high;
}
int main()
{
int n,m,i,a[N],b[N];
double x1,x2,y1,y2;
point p;
segment s[N];
while()
{
scanf("%d",&n);
if(n==) break;
scanf("%d%lf%lf%lf%lf",&m,&x1,&y1,&x2,&y2);
s[].p1.x=x1;
s[].p1.y=y1;
s[].p2.x=x1;
s[].p2.y=y2;
for(i=;i<=n;i++)
{
scanf("%lf%lf",&s[i].p1.x,&s[i].p2.x);
s[i].p1.y=y1;
s[i].p2.y=y2;
}
s[i].p1.x=x2;
s[i].p1.y=y1;
s[i].p2.x=x2;
s[i].p2.y=y2;
Quick_sort(s,,n+);
for(i=;i<N;i++) a[i]=;
for(i=;i<m;i++)
{
scanf("%lf%lf",&p.x,&p.y);
a[BinSearch(s,n+,p)]++;
}
for(i=;i<N;i++) b[i]=;
for(i=;i<N;i++) b[a[i]]++;
printf("Box\n");
for(i=;i<N;i++) if(b[i]) printf("%d: %d\n",i,b[i]);
}
return ;
}
PKU 2398