## 【POJ-2398】Toy Storage【还是叉积判三点旋向】

【POJ-2398】Toy Storage【还是叉积判三点旋向】

Solution:

【POJ-2318】TOYS【叉积判定三点旋向】处理方法完全相同，把那个结果的数组再重新用另外一个数组当做桶来处理一下，就可以了。需要注意的是，这道题给出的分隔板不再是从左到右顺序给出的，需要预先排序。

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

using namespace std;

const int LIM = 1000 + 10;
struct node {
int xs, xe;
bool operator < (const node &n) const {
return xs < n.xs;
}
};
int ans[LIM];
node x[LIM];
int cnt[LIM];

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++) {
printf("Box\n");
memset(cnt, 0, sizeof cnt);
memset(ans, 0, sizeof ans);
scanf("%d%d%d%d%d", &m, &x1, &y1, &x2, &y2);
for (int i = 0; i < n; i++) {
scanf("%d%d", &x[i].xs, &x[i].xe);
}
sort(x, x + n);
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 - x[mid].xe, b - y2, x[mid].xs - x[mid].xe, y1 - y2);
if (flag < 0) r = mid;
else if (flag > 0) l = mid + 1;
}
cnt[l]++;
}
for (int i = 0; i <= n; i++) ans[cnt[i]]++;
for (int i = 1; i <= m; i++)
if (ans[i]) printf("%d: %d\n", i, ans[i]);
}
return 0;
}
```