Toy Storage POJ——2398(同POJ-2318)

这个题跟POJ-2318的区别在于处理前要对板按照从x从小到大排序
  1 #include <map>
  2 #include <set>
  3 #include <cmath>
  4 #include <queue>
  5 #include <string>
  6 #include <vector>
  7 #include <cstdio>
  8 #include <cstring>
  9 #include <iostream>
 10 #include <algorithm>
 11 #define forn(i, n) for (int i = 0; i < (n); i++)
 12 #define forab(i, a, b) for (int i = (a); i <= (b); i++)
 13 #define forba(i, b, a) for (int i = (b); i >= (a); i--)
 14 #define mset(a, n) memset(a, n, sizeof(a))
 15 #define fast ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
 16 #define fi first
 17 #define se second
 18 using namespace std;
 19 #define N 5005
 20 #define maxn 1005
 21 #define inf 0x3f3f3f3f
 22 #define ll long long
 23 #define ull unsigned long long
 24 struct P
 25 {
 26     int x, y;
 27     
 28     P(){}
 29     P(int _x,int _y)
 30     {
 31         x = _x;
 32         y = _y;
 33     }
 34     
 35     P operator - (const P &b) const
 36     {
 37         return P(x - b.x, y - b.y);
 38     }
 39     
 40     int operator * (const P &b) const
 41     {
 42         return x * b.x + y * b.y;
 43     }
 44     
 45     int operator ^ (const P &b) const
 46     {
 47         return x * b.y - y * b.x;
 48     }
 49     
 50 };
 51 struct L
 52 {
 53     P p1, p2;
 54     
 55     L(){}
 56     L(P _p1,P _p2)
 57     {
 58         p1 = _p1;
 59         p2 = _p2;
 60     }
 61     friend bool operator < (const L &a,const L &b) 
 62     {
 63         return a.p1.x < b.p1.x;     
 64     } 
 65     
 66 }a[N];
 67 int cal(P x1,P x2,P x3)
 68 {
 69     return (x2 - x1) ^ (x3 - x1);
 70 }
 71 int ans[N], n, m;
 72 int x1, x2, Y1, y2;
 73 int cnt[N];
 74 int main()
 75 {
 76     while(~scanf("%d",&n))
 77     {
 78         if(!n) break;
 79         scanf("%d %d %d %d %d",&m ,&x1 ,&Y1 ,&x2 ,&y2);
 80         forn(i,n)
 81         {
 82             int f, b;
 83             scanf("%d %d",&f ,&b);
 84             a[i] = L(P(f,Y1), P(b,y2));
 85         }
 86         a[n] = L(P(x2,Y1), P(x2,y2));
 87         sort(a,a+n+1);
 88         mset(ans, 0);
 89         mset(cnt, 0);
 90         forab(i,1,m)
 91         {
 92             int x, y;
 93             scanf("%d %d",&x, &y);
 94             P p(x, y);
 95             if(cal(p, a[0].p1, a[0].p2) < 0)
 96             {
 97                 ans[0]++;
 98                 continue;
 99             }
100             forab(j,1,n)
101             {
102                 if(cal(p, a[j-1].p1, a[j-1].p2) > 0 && cal(p, a[j].p1, a[j].p2) < 0)
103                 {
104                     ans[j]++;
105                     break;
106                 }
107             }
108         }
109         
110         forab(i,0,n)
111         {
112             cnt[ans[i]]++;
113         }
114         cout<<"Box"<<endl;
115         forab(i,1,m)
116         {
117             if(cnt[i]) cout<<i<<": "<<cnt[i]<<endl;
118         }
119     }
120 }