POJ2318TOYS(叉积判断点与直线位置)

题意：一个矩形被分成了n + 1块，然后给出m个点，求每个点会落在哪一块中，输出每块的点的个数

就是判断点与直线的位置，点在直线的逆时针方向叉积 < 0，点在直线的顺时针方向叉积 > 0

 1 // 可以选择二分查找
 2 #include <iostream>
 3 #include <algorithm>
 4 #include <cstdio>
 5 #include <cstring>
 6 using namespace std;
 7 typedef long long LL;
 8 const int Max = 1000 + 10;
 9 int num[Max];
10 //int ux[Max], dx[Max];
11 struct Point
12 {
13     LL ux, dx;
14 };
15 LL Cross(LL x1, LL y1, LL x2, LL y2)
16 {
17     return x1 * y2 - y1 * x2;
18 }
19 int main()
20 {
21     int n, m, x1, x2, y1, y2;
22     while (scanf("%d", &n) != EOF && n)
23     {
24         scanf("%d%d%d%d%d", &m, &x1, &y1, &x2, &y2);
25         for(int i = 1; i <= n; i++)
26             scanf("%d%d", &ux[i], &dx[i]);
27         ux[n + 1] = x2;  // 把最后边界也算进去
28         dx[n + 1] = x2;
29         memset(num, 0, sizeof(num));
30         int x, y, l, r, mid;
31         for (int i = 1; i <= m; i++)
32         {
33             scanf("%d%d", &x, &y);
34             if (!(x >= x1 && x <= x2 && y >= y2 && y <= y1)) // 不在矩形内
35                 continue;
36             l = 1, r = n + 1;
37             while (l < r)
38             {
39                 mid = (l + r) / 2;
40                 if (Cross(x - dx[mid], y - y2, ux[mid] - dx[mid], y1 - y2) > 0)  // 如果 大于 0 说明 点在直线 右侧，所以改变左区间
41                     l = mid + 1;
42                 else
43                     r = mid; // r始终是满足条件的
44             }
45             num[r - 1]++;
46             /*
47             for (int j = 1; j <= n + 1; j++)
48             {
49                 if ( Cross(x - dx[j], y - y2, ux[j] - dx[j], y1 - y2) <= 0)
50                 {
51                     num[j - 1]++;
52                     break;
53                 }
54             }
55             */
56         }
57         for (int i = 0; i <= n; i++)
58             printf("%d: %d
", i, num[i]);
59         printf("
");
60     }
61     return 0;
62 }

View Code