题意 ： 给你n块板的坐标，m个玩具的具体坐标，2318中板是有序的，而2398无序需要自己排序，2318要求输出的是每个区间内的玩具数，而2318要求输出的是有 i 个玩具的区间有几个。
思路 ： 两个题基本差不多，只不过2398排一下序，然后再找个数组标记一下就行。
这个题我一开始没想到用二分，判断了点在四边形内但是没写下去，然后看了网上的二分区间，利用叉积判断点在左边还是右边。
2318代码：
1 #include <stdio.h> 2 #include <string.h> 3 #include <math.h> 4 #include <iostream> 5 6 using namespace std ; 7 8 struct point 9 { 10 int x,y ; 11 }p ; 12 struct line 13 { 14 point a,b ; 15 } eline[5120] ; 16 17 int s[5120] ; 18 19 int xmult(point p1,point p2,point p0) 20 { 21 return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y) ; 22 } 23 24 void binary_searc(point p,int a) 25 { 26 int l = 0, r = a-1 ,mid ; 27 while(l < r) 28 { 29 mid = (l + r) /2 ; 30 if(xmult(p,eline[mid].a,eline[mid].b) > 0) l = mid+1 ; 31 else r = mid ; 32 } 33 if(xmult(p,eline[l].a,eline[l].b) < 0) s[l] ++ ; 34 else s[l+1] ++ ; 35 } 36 int main() 37 { 38 int m,n,x1,x2,y1,y2 ; 39 while(scanf("%d",&n) != EOF) 40 { 41 if(n == 0) break ; 42 scanf("%d %d %d %d %d",&m,&x1,&y1,&x2,&y2) ; 43 memset(s,0,sizeof(s)) ; 44 for(int i = 0 ; i < n ; i++) 45 { 46 scanf("%d %d",&eline[i].a.x,&eline[i].b.x) ; 47 eline[i].a.y = y1 ; 48 eline[i].b.y = y2 ; 49 } 50 for(int i = 0 ; i < m ; i++) 51 { 52 scanf("%d %d",&p.x,&p.y) ; 53 binary_searc(p,n) ; 54 } 55 for(int i = 0 ; i <= n ; i++) 56 printf("%d: %d ",i,s[i]) ; 57 printf(" ") ; 58 } 59 return 0 ; 60 }
2398代码 ：
1 #include <stdio.h> 2 #include <string.h> 3 #include <math.h> 4 #include <iostream> 5 #include <algorithm> 6 7 using namespace std ; 8 9 struct point 10 { 11 int x,y ; 12 }p ; 13 struct line 14 { 15 point a,b ; 16 } eline[1120] ; 17 18 int s[1120],s1[1120] ; 19 20 int xmult(point p1,point p2,point p0) 21 { 22 return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y) ; 23 } 24 25 int cmp(const line &aa,const line &bb) 26 { 27 if (min(aa.a.x, aa.b.x) == min(bb.a.x, aa.b.x)) 28 return max(aa.a.x, aa.b.x) < max(bb.a.x, bb.b.x); 29 return min(aa.a.x, aa.b.x) < min(bb.a.x, aa.b.x); 30 } 31 void binary_searc(point p,int a) 32 { 33 int l = 0, r = a-1 ,mid ; 34 while(l < r) 35 { 36 mid = (l + r) /2 ; 37 if(xmult(p,eline[mid].a,eline[mid].b) > 0) l = mid+1 ; 38 else r = mid ; 39 } 40 if(xmult(p,eline[l].a,eline[l].b) < 0) s[l] ++ ; 41 else s[l+1] ++ ; 42 } 43 int main() 44 { 45 int m,n,x1,x2,y1,y2 ; 46 while(scanf("%d",&n) != EOF) 47 { 48 if(n == 0) break ; 49 scanf("%d %d %d %d %d",&m,&x1,&y1,&x2,&y2) ; 50 memset(s,0,sizeof(s)) ; 51 memset(s1,0,sizeof(s1)) ; 52 for(int i = 0 ; i < n ; i++) 53 { 54 scanf("%d %d",&eline[i].a.x,&eline[i].b.x) ; 55 eline[i].a.y = y1 ; 56 eline[i].b.y = y2 ; 57 } 58 sort(eline,eline+n,cmp) ; 59 for(int i = 0 ; i < m ; i++) 60 { 61 scanf("%d %d",&p.x,&p.y) ; 62 binary_searc(p,n) ; 63 } 64 for(int i = 0 ; i <= n ; i++) 65 s1[s[i]] ++ ; 66 printf("Box ") ; 67 for(int i = 1 ; i <= m ; i++) 68 { 69 if(s1[i] != 0) 70 printf("%d: %d ",i,s1[i]) ; 71 } 72 // for(int i = 0 ; i <= n ; i++) 73 // printf("%d: %d ",i,s[i]) ; 74 // printf(" ") ; 75 } 76 return 0 ; 77 }