#P18104. Hockey Hog
Hockey Hog
Hockey Hog
豪猪们的冰球场是一个严格凸多边形 ,顶点依次为 。每个顶点 处有一个编号为 的球门。
冰球场完全位于另一个严格凸多边形 的内部, 的顶点为 。 围出的内部是危险区域,观众不能站在其中,但可以站在 的边界上或外部。
球门朝向球场内部。每个球门的外侧有两块不透明挡板,分别沿该顶点相邻的两条球场边放置。
位于 的观众能看到向球门 打进的球,当且仅当从 出发、经过 的射线位于多边形 在 处的内角内部或内角边界上。否则,该球门的挡板会遮住视线。球门 的挡板只影响对球门 的观察,不影响其他球门。
由于豪猪力量太大,每个球门在被打进一个球后就会立即损坏,之后不再使用。所有球门均损坏后,比赛结束。进球顺序由排列 给出:第 个球打进球门 。
在第 次进球前,观众可以重新选择一个合法位置 ,随后一直留在该位置直到比赛结束。
对于每个 ,独立地求出:若在第 次进球前选择最佳位置,最多能看到之后打进球门 的多少个球?
输入格式
第一行一个整数 (),表示测试组数。
每组数据的第一行包含两个整数 ()。
接下来 行,每行两个整数 ,表示 的坐标。顶点按逆时针顺序给出。
接下来 行,每行两个整数 ,表示 的坐标。顶点同样按逆时针顺序给出。
所有坐标的绝对值均不超过 。保证 都严格凸,且 完全位于 的严格内部。
最后一行是 的一个排列 。
保证所有测试组的 ,且 。
输出格式
对于每组数据输出一行 个整数。第 个数表示在第 次进球前选择位置后,最多能看到的剩余进球数。
样例
2
3 4
1 1
3 1
1 3
0 0
4 0
4 4
0 4
3 2 1
4 3
-1 2
1 2
2 4
-2 4
0 -1
6 5
-6 5
1 2 3 4
1 1 1
2 2 1 1
在第二组数据中:
- 第一次进球前,可站在 ,看到球门1、2的两次进球。
- 第二次进球前,球门1已经损坏。可站在 边界上的 ,看到球门2、3的两次进球。
- 第三次进球前,只剩球门3、4,无法在合法位置同时看到两者。站在 边界上的 可看到球门4。
- 第四次进球前,仍可站在 看到最后一次进球。