1 // 题意:问你每个区域有多少个点
2 // 思路:数据小可以直接暴力
3 // 也可以二分区间
4
5 #include <cstdio>
6 #include <cstring>
7 #include <iostream>
8 #include <algorithm>
9 #include <map>
10 #include <set>
11 #include <queue>
12 #include <stdlib.h>
13 #include <cmath>
14 using namespace std;
15 typedef long long LL;
16 const LL inf = 1e18;
17 const int N = 5000;
18
19 struct Point{
20 int x,y;
21 Point(){}
22 Point(int _x,int _y){
23 x=_x;y=_y;
24 }
25 Point operator -(const Point &b)const{
26 return Point(x-b.x,y-b.y);
27 }
28 int operator *(const Point &b)const{
29 return x*b.x+y*b.y;
30 }
31 int operator ^(const Point &b)const{
32 return x*b.y-y*b.x;
33 }
34 };
35
36 struct Line{
37 Point s,e;
38 Line(){}
39 Line(Point _s,Point _e){
40 s=_s,e=_e;
41 }
42 };
43
44 int xmult(Point p0,Point p1,Point p2){
45 return (p1-p0)^(p2-p0);
46 }
47
48 Line line[N];
49 int ans[N];
50 int main(){
51 int n,m,x1,y1,x2,y2;
52 bool first = true;
53 while(~scanf("%d",&n)&&n){
54 if(first) first=false;
55 else printf("
");
56 scanf("%d%d%d%d%d",&m,&x1,&y1,&x2,&y2);
57 for(int i=0;i<n;i++){
58 int x,y;
59 scanf("%d%d",&x,&y);
60 line[i]=Line(Point(x,y1),Point(y,y2));
61 }
62 line[n]=Line(Point(x2,y1),Point(x2,y2));
63 int x,y;
64 Point p;
65 memset(ans,0,sizeof(ans));
66 int tem;
67 while(m--){
68 scanf("%d%d",&x,&y);
69 p = Point(x,y);
70 int l=0,r=n,mid;
71 while(l<=r){
72 mid=(l+r)>>1;
73 if(xmult(p,line[mid].s,line[mid].e)<0){
74 tem=mid;
75 r=mid-1;
76 }
77 else l=mid+1;
78 }
79 ans[tem]++;
80 }
81 for(int i=0;i<=n;i++) printf("%d: %d
",i,ans[i]);
82 }
83 return 0;
84 }
1 // POJ 2398和2318差不多 多了排序和统计输出
2
3 #include <cstdio>
4 #include <cstring>
5 #include <iostream>
6 #include <algorithm>
7 #include <map>
8 #include <set>
9 #include <queue>
10 #include <stdlib.h>
11 #include <cmath>
12 using namespace std;
13 typedef long long LL;
14 const LL inf = 1e18;
15 const int N = 5000;
16
17 struct Point{
18 int x,y;
19 Point(){}
20 Point(int _x,int _y){
21 x=_x;y=_y;
22 }
23 Point operator -(const Point &b)const{
24 return Point(x-b.x,y-b.y);
25 }
26 int operator *(const Point &b)const{
27 return x*b.x+y*b.y;
28 }
29 int operator ^(const Point &b)const{
30 return x*b.y-y*b.x;
31 }
32 };
33
34 struct Line{
35 Point s,e;
36 Line(){}
37 Line(Point _s,Point _e){
38 s=_s,e=_e;
39 }
40 };
41
42 int xmult(Point p0,Point p1,Point p2){
43 return (p1-p0)^(p2-p0);
44 }
45
46 bool cmp(Line a,Line b){
47 return a.s.x<b.s.x;
48 }
49
50 Line line[N];
51 int ans[N];
52 int num[N];
53 int main(){
54 int n,m,x1,y1,x2,y2;
55 while(~scanf("%d",&n)&&n){
56 memset(num,0,sizeof(num));
57 scanf("%d%d%d%d%d",&m,&x1,&y1,&x2,&y2);
58 for(int i=0;i<n;i++){
59 int x,y;
60 scanf("%d%d",&x,&y);
61 line[i]=Line(Point(x,y1),Point(y,y2));
62 }
63 line[n]=Line(Point(x2,y1),Point(x2,y2));
64 sort(line,line+n+1,cmp);
65 int x,y;
66 Point p;
67 memset(ans,0,sizeof(ans));
68 int tem;
69 while(m--){
70 scanf("%d%d",&x,&y);
71 p = Point(x,y);
72 int l=0,r=n,mid;
73 while(l<=r){
74 mid=(l+r)>>1;
75 if(xmult(p,line[mid].s,line[mid].e)<0){
76 tem=mid;
77 r=mid-1;
78 }
79 else l=mid+1;
80 }
81 ans[tem]++;
82 }
83 for(int i=0;i<=n;i++){
84 num[ans[i]]++;
85 }
86 printf("Box
");
87 for(int i=1;i<=n;i++) {
88 if(num[i]>0)
89 printf("%d: %d
",i,num[i]);
90 }
91 }
92 return 0;
93 }