【解题报告】PKU 2318 TOYS AND PKU 2398 Toy Storage

题目连接： http://poj.org/problem?id=2318 http://poj.org/problem?id=2398

两题类似的题目，2398是2318的升级版。

题目大概是说，有一个矩形的柜子，中间有一些隔板。告诉你每个隔板的坐标，还有一些玩具的坐标，统计玩具在哪个格子里。

这题的思路很简单，如果玩具在某个隔板的左边和右边叉乘的正负是不同的。如图：

图中点P在线段CD的左边，则向量PC和向量PD叉乘结果小于0。反之P在AB的左边，向量PA叉乘PB大于0。

因此利用这个性质以及排序好的线段列表，通过二分思想，可以快速知道点在哪个格子内。

代码：

  1 #include<stdio.h>
  2 #include<math.h>
  3 #define PI 3.14159265358979323846
  4 #define MAX(x,y) ((x)>(y)?(x):(y))
  5 #define MIN(x,y) ((x)<(y)?(x):(y))
  6 #define ABS(x) (((x)>0)?(x):(-(x)))
  7 #define SIGN(x) (((x)<0)?-1:1)
  8 #define EPS 0.000001/*精度控制*/
  9 #define N 5005
 10 /*坐标的定义*/
 11 typedef double coo;/*int*/
 12 /*点、向量*/
 13 typedef struct POINT
 14 {
 15     coo x,y;
 16 }point,vector;
 17 /*线段*/
 18 typedef struct SEGMENT
 19 {
 20     point p1,p2;/*p[2];*/
 21 }segment;
 22 /*判相等*/
 23 int is_equel(double a,double b)
 24 {
 25     double c=ABS(a-b);
 26     if(c<=EPS) return 1;/*相等*/
 27     else return 0;/*不相等*/
 28 }
 29 /*向量的减法p1-p2*/
 30 vector vector_minus(vector p1,vector p2)
 31 {
 32     vector p;
 33     p.x=p1.x-p2.x;
 34     p.y=p1.y-p2.y;
 35     return p;
 36 }
 37 /*向量叉乘*/
 38 double cross_product(vector p1,vector p2)
 39 {/*x1y2-x2y1*/
 40     return p1.x*p2.y-p1.y*p2.x;
 41 }
 42 int bijiao(segment s1,segment s2)/*比较两个线段的位置<  */
 43 {
 44     if(s1.p1.x<s2.p1.x) return 1;
 45     if(s1.p1.x==s2.p1.x&&s1.p2.x<s2.p2.x) return 1;
 46     return 0;
 47 }
 48 int Partition(segment r[],int low,int high)/*升序*/
 49 /*返回支点最终位置*/
 50 {
 51     segment x;/*类型具体*/
 52     if(low>high) return 0;
 53     if(low==high) return low;
 54     x=r[low];
 55     while(low<high)
 56     {
 57         while(low<high&&bijiao(x,r[high])) high--;    /*<*/
 58         if(low<high){r[low]=r[high];low++;}
 59         while(low<high&&bijiao(r[low],x)) low++;        /*>*/
 60         if(low<high){r[high]=r[low];high--;}
 61     }
 62     r[low]=x;
 63     return low;
 64 }
 65 void Quick_sort(segment r[],int m,int n) /*排序从r[m]到r[n]*/
 66 {
 67     int i;
 68     if(m>=n) return;
 69     i=Partition(r,m,n);
 70     Quick_sort(r,m,i-1);
 71     Quick_sort(r,i+1,n);
 72 }
 73 
 74 int BinSearch(segment a[],int n,point k)/*在有序的数组a[0]~a[n-1]中查找k元素*/
 75 {
 76     int low=0,high=n-1,mid;
 77     while(low<=high)
 78     {
 79         mid=low+((high-low)/2);
 80         if(cross_product(vector_minus(a[mid].p1,k),vector_minus(a[mid].p2,k))<0) high=mid-1;/*线段在右边*/
 81         else low=mid+1;
 82     }
 83     if(low>high) return high;
 84 }
 85 int main()
 86 {
 87     int n,m,i,a[N],b[N];
 88     double x1,x2,y1,y2;
 89     point p;
 90     segment s[N];
 91     while(1)
 92     {
 93         scanf("%d",&n);
 94         if(n==0) break;
 95         scanf("%d%lf%lf%lf%lf",&m,&x1,&y1,&x2,&y2);
 96         s[0].p1.x=x1;
 97         s[0].p1.y=y1;
 98         s[0].p2.x=x1;
 99         s[0].p2.y=y2;
100         for(i=1;i<=n;i++)
101         {
102             scanf("%lf%lf",&s[i].p1.x,&s[i].p2.x);
103             s[i].p1.y=y1;
104             s[i].p2.y=y2;
105         }
106         s[i].p1.x=x2;
107         s[i].p1.y=y1;
108         s[i].p2.x=x2;
109         s[i].p2.y=y2;
110         Quick_sort(s,0,n+1);
111         for(i=0;i<N;i++) a[i]=0;
112         for(i=0;i<m;i++)
113         {
114             scanf("%lf%lf",&p.x,&p.y);
115             a[BinSearch(s,n+2,p)]++;
116         }
117         for(i=0;i<N;i++) b[i]=0;
118         for(i=0;i<N;i++) b[a[i]]++;
119         printf("Box
");
120         for(i=1;i<N;i++) if(b[i]) printf("%d: %d
",i,b[i]);
121     }
122     return 0;
123 }

PKU 2398