问题陈述
你是下次选举候选人X先生的支持者。 X先生计划在车站前进行街头演讲,他打算在尽可能多的选民能看到的场合进行演讲。
车站前被视为一个二维平面,上面存在$N$个障碍物和$M$名选民。 每个障碍物用多边形表示,多边形内部的区域为障碍物。多边形的边缘不包含在障碍物内。 另外,选民用平面上的点表示。 如果连接某个选民的位置与X先生的位置的线段上没有障碍物,那么该选民可以看到X先生。
你的工作是根据车站前的障碍物和选民的信息,寻找一个能被最多选民看到的位置。 求出最多可以被多少名选民看到并发表演说。
输入
输入将以以下格式给出。
$N$ $M$
$polygon_1$
$polygon_2$
$...$
$polygon_N$
$x_1$ $y_1$
$x_2$ $y_2$
$...$
$x_M$ $y_M$
数据集的第一行由两个整数组成,中间有一个空格,分别是$N$和$M$。 $N$$(1 \le n \le 5)$ 是车站前的障碍物数量,$M$ (1 \le M \le 10)$ 是车站前的投票人数。 从以下行中,可以获得$N$障碍的信息。代表一个障碍的输入格式如下。
$L$
$x_1$ $y_1$
$x_2$ $y_2$
$...$
$x_L$ $y_L$
每个障碍信息的第一行是表示该障碍的多形态中包含的边数$L$。 以下$L$直线包含一组整数,代表多边形边计的坐标,方向为逆时针方向。构成障碍的边总数为15美元或更少。
在获得$N$障碍信息后,$M$线会被赋予一组整数,代表选民的坐标。
此外,每个 sutokeesu 必须满足以下条件:
- $ 0 \le |x_i|, |y_i| \le 20 $
- 多边形顶点的坐标或选民的位置都彼此不同。
- 多边形顶点之间的三点或选民位置坐标不能位于同一条直线上。
- 两个不同的多边形没有交集。
- 每个多边形都没有自交点。
- 多边形内没有选民。
输出
在一行上打印能够看到演讲的选民的最大数量。
示例输入 1
1 2 4 5 5 15 5 15 15 5 15 0 10 20 10
样本输入 1 的输出
2
示例输入 2
1 2 6 0 0 20 0 12 9 20 20 0 20 8 11 1 10 19 10
样本输入 2 的输出
1
示例输入 3
4 2 3 0 0 20 0 20 1 3 0 18 19 19 19 20 3 3 2 4 2 4 17 3 16 3 17 3 17 18 2 9 18 10
样本输入 3 的输出
1
示例输入 4
3 3 3 0 -2 -1 -3 -1 -6 3 2 2 3 2 4 3 3 -4 4 -4 5 -5 6 0 -3 3 3 -5 5
样本输入 4 的输出
3
示例输入 5
2 2 4 2 0 1 2 -1 2 -2 0 4 3 3 3 4 -3 4 -3 3 2 1 -2 1
样本输入 5 的输出
2
示例输入 6
1 1 4 1 1 -1 1 -1 -1 1 -1 0 2
样本输入 6 的输出
1
每个输入示例的障碍物和选民的放置如下图所示。