TOYS POJ-2318(叉乘判断点与直线的关系)

叉乘如何判断在我的另一篇博客已经讲过。(其实就是懒得再打一遍了
  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     
 62 }a[N];
 63 int cal(P x1,P x2,P x3)
 64 {
 65     return (x2 - x1) ^ (x3 - x1);
 66 }
 67 int ans[N], n, m;
 68 int x1, x2, Y1, y2;
 69 int main()
 70 {
 71     while(~scanf("%d",&n))
 72     {
 73         if(!n) break;
 74         scanf("%d %d %d %d %d",&m ,&x1 ,&Y1 ,&x2 ,&y2);
 75         forn(i,n)
 76         {
 77             int f, b;
 78             scanf("%d %d",&f ,&b);
 79             a[i] = L(P(f,Y1), P(b,y2));
 80         }
 81         a[n] = L(P(x2,Y1), P(x2,y2));
 82         mset(ans, 0);
 83         forab(i,1,m)
 84         {
 85             int x, y;
 86             scanf("%d %d",&x, &y);
 87             P p(x, y);
 88             if(cal(p, a[0].p1, a[0].p2) < 0)
 89             {
 90                 ans[0]++;
 91                 continue;
 92             }
 93             forab(j,1,n)
 94             {
 95                 if(cal(p, a[j-1].p1, a[j-1].p2) > 0 && cal(p, a[j].p1, a[j].p2) < 0)
 96                 {
 97                     ans[j]++;
 98                     break;
 99                 }
100             }
101         }
102         forab(i,0,n)
103         {
104             printf("%d: %d
",i ,ans[i]);
105         }
106         printf("
");
107     }
108 }