POJ 2398 Toy Storage（叉积+二分）

 1 /*
 2 ** POJ 2398 Toy Storage
 3 ** Created by Rayn @@ 2014/05/05
 4 */
 5 #include <cstdio>
 6 #include <cstring>
 7 #include <algorithm>
 8 using namespace std;
 9 const int MAX = 1010;
10 const int INF = 0x3f3f3f3f;
11 
12 struct Point {
13     double x, y;
14     Point(double a=0, double b=0): x(a), y(b) {}
15 } dot[MAX];
16 
17 struct Line {
18     double up, low;
19     bool operator < (const Line& rhs) const {
20         double x1 = min(up, low);
21         double x2 = min(rhs.up, rhs.low);
22         if(x1 == x2)
23             return max(up, low) < max(rhs.up, rhs.low);
24         else
25             return x1 < x2;
26     }
27 } line[MAX];
28 
29 int num[MAX], ans[MAX];
30 
31 double Cross(Point A, Point B, Point C)
32 {
33     return (C.x-A.x)*(B.y-A.y)-(B.x-A.x)*(C.y-A.y);
34 }
35 int main()
36 {
37 #ifdef _Rayn
38     freopen("in.txt", "r", stdin);
39 #endif
40 
41     int n, m;
42     double x1, y1, x2, y2;
43 
44     while(scanf("%d", &n) != EOF && n)
45     {
46         scanf("%d%lf%lf%lf%lf", &m, &x1, &y1, &x2, &y2);
47         //printf("%d %d\n", n, m);
48         for(int i=0; i<n; ++i)
49         {
50             scanf("%lf%lf", &line[i].up, &line[i].low);
51         }
52         sort(line, line+n);
53         line[n].up = line[n].low = x2;
54 
55         memset(num, 0, sizeof(num));
56         memset(ans, 0, sizeof(ans));
57         for(int i=0; i<m; ++i)
58         {
59             scanf("%lf%lf", &dot[i].x, &dot[i].y);
60             int left = 0, right = n, mid = 0;
61             while(left <= right)
62             {
63                 mid = (left + right) / 2;
64                 Point b(line[mid].low, y2);
65                 Point c(line[mid].up, y1);
66                 if(Cross(dot[i], b, c) > 0)
67                     left = mid + 1;
68                 else
69                     right = mid - 1;
70             }
71             num[left]++;
72         }
73         for(int i=0; i<=n; ++i)
74         {
75             if(num[i])
76                 ans[num[i]]++;
77         }
78         printf("Box\n");
79         for(int i=0; i<=n; ++i)
80         {
81             if(ans[i])
82                 printf("%d: %d\n", i, ans[i]);
83         }
84     }
85     return 0;
86 }