## 【POJ-2318】TOYS【叉积判定三点旋向】

【POJ-2318】TOYS【叉积判定三点旋向】

Solution:

```#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>

using namespace std;

const int LIM = 5000 + 10;
int ans[LIM];
int xs[LIM], xe[LIM];
int cnt[LIM];

char ch = getchar();
x = 0;
for (; ch < '0' || ch > '9'; ch = getchar());
for (; ch >='0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';
}

int cross(int ax, int ay, int bx, int by) {
int tmp = ax * by - bx * ay;
if (tmp == 0) return 0;
else if (tmp < 0) return -1;
else return 1;
}

int main(void) {
int n, m, x1, y1, x2, y2, a, b;
for (int k = 0; ~scanf("%d", &n) && n; k++) {
if (k) putchar('\n');
memset(cnt, 0, sizeof cnt);
scanf("%d%d%d%d%d", &m, &x1, &y1, &x2, &y2);
for (int i = 0; i < n; i++) {
scanf("%d%d", xs + i, xe + i);
}
for (int i = 0; i < m; i++) {
scanf("%d%d", &a, &b);
int l = 0, r = n;
while (l < r) {
int mid = (l + r) >> 1;
int flag = cross(a - xe[mid], b - y2, xs[mid] - xe[mid], y1 - y2);
if (flag < 0) r = mid;
else if (flag > 0) l = mid + 1;
}
cnt[l]++;
}
for (int i = 0; i <= n; i++) printf("%d: %d\n", i, cnt[i]);
}
return 0;
}
```