#jag2016secretspringe. [jag2016secretspring_e]選挙活動

[jag2016secretspring_e]選挙活動

题目描述

你是候选人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(1N5)(1 \le N \le 5)表示广场上的障碍物数量,M(1M10)(1 \le M \le 10)表示广场上的选民数量。接下来的N行提供了障碍物的信息。一组表示一个障碍物的输入如下所示。

L
x_1 y_1
x_2 y_2
...
x_L y_L

障碍物信息的第一行是表示该障碍物多边形的顶点数L。随后的L行按逆时针方向记录了多边形的顶点坐标。需要注意的是,一个障碍物的顶点总数不超过15个。

障碍物信息之后是M行,表示选民的坐标。

同时,每个测试用例需要满足以下条件:

  1. 0xi,yi20 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

```plain
2```

---

### 样例输入2

```plain
1 2
6
0 0
20 0
12 9
20 20
0 20
8 11
1 10
19 10```

### 样例输出2

```plain
1```

---

### 样例输入3

```plain
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

```plain
1```

---

### 样例输入4

```plain
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

```plain
3```

---

### 样例输入5

```plain
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

```plain
2```

---

### 样例输入6

```plain
1 1
4
1 1
-1 1
-1 -1
1 -1
0 2```

### 样例输出6

```plain
1```