# 题目

{% fold 点击显/隐题目 %}

John's parents came up with the following idea. They put cardboard partitions into the box. Even if John keeps throwing his toys into the box, at least toys that get thrown into different bins stay separated. The following diagram shows a top view of an example toy box.

For this problem, you are asked to determine how many toys fall into each partition as John throws them into the toy box.

0: 2

1: 2

2: 2

3: 2

4: 2

# 题解

使用向量判断点在直线哪一侧

如 判断点{% raw %}$P_0${% endraw %}在线段{% raw %}$P_1P_2${% endraw %}的哪一侧:

$\vec {P_1P_2} \times \vec {P_1P_0}$

若该值大于$0$,则在顺时针方向,小于$0$在逆时针方向,等于$0$在线段上

注意判断的时候应该使用二分判断

写的时候初始化写错变量了,调了好久

# 代码

{% fold 点击显/隐代码 %}```cpp TOYS https://github.com/OhYee/sourcecode/tree/master/ACM 代码备份

#include

#include

#include

using namespace std;

#define Log(format, ...) printf(format, ##**VA_ARGS**)

/* 向量模板 */

typedef complex

int Cross(Vector a, Vector b) {

return a.real() * b.imag() - a.imag() * b.real();

}

int Dot(Vector a, Vector b) {

return a.real() * b.real() + a.imag() * b.imag();

}

const int maxn = 5005;

Vector P1[maxn];

Vector P2[maxn];

int cnt[maxn];

bool Could(Vector p, Vector L) { return (Cross(L, p) >= 0); }

int Division(int l, int r, Vector p) {

// printf("%d %d (%.f,%.f)\n", l, r, p.real(), p.imag());

if (r - l == 1)

return l;

```
int mid = (l + r) >> 1;
if (Could(p - P1[mid], P2[mid] - P1[mid]))
return Division(l, mid, p);
else
return Division(mid, r, p);
```

}

int main() {

int n, m, x1, y1, x2, y2;

while (scanf("%d%d%d%d%d%d", &n, &m, &x1, &y1, &x2, &y2), n != 0) {

P1[0] = Vector(x1, y2);

P2[0] = Vector(x1, y1);

for (int i = 1; i <= n; ++i) {

int u, l;

scanf("%d%d", &u, &l);

P2[i] = Vector(u, y1);

P1[i] = Vector(l, y2);

}

P1[n + 1] = Vector(x2, y2);

P2[n + 1] = Vector(x2, y1);

```
// for (int i = 0; i <= n + 1; ++i) {
// printf("%d : (%.f,%.f) -> (%.f,%.f)\n", i, P1[i].real(),
// P1[i].imag(), P2[i].real(), P2[i].imag());
// }
memset(cnt, 0, sizeof(int) * (n + 5));
for (int i = 0; i < m; ++i) {
int x, y;
scanf("%d%d", &x, &y);
cnt[Division(0, n + 1, Vector(x, y))]++;
}
for (int i = 0; i <= n; ++i)
printf("%d: %d\n", i, cnt[i]);
printf("\n");
}
return 0;
```

}

{% endfold %}