← 返回题目列表

AtCoder · jag2016secretspring_e

E. 选举活动

中文机器翻译题面 查看原题

问题陈述

你是下次选举候选人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 必须满足以下条件:

  1. $ 0 \le |x_i|, |y_i| \le 20 $
  2. 多边形顶点的坐标或选民的位置都彼此不同。
  3. 多边形顶点之间的三点或选民位置坐标不能位于同一条直线上。
  4. 两个不同的多边形没有交集。
  5. 每个多边形都没有自交点。
  6. 多边形内没有选民。

输出

在一行上打印能够看到演讲的选民的最大数量。



示例输入 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

每个输入示例的障碍物和选民的放置如下图所示。