P17430 [ICPC 2018 Xuzhou R] Rikka with Illuminations

Rikka 热爱凸多边形，因此她决定安装一些照明装置来装点多边形。 现在，她有一个具有 $n$ 条边的大凸多边形。她还在多边形外部严格地选取了 $m$ 个不同的点，这些点都是安装照明装置的合法位置。 一个照明装置可以照亮多边形的一部分外部边界。 Rikka 希望安装若干照明装置，以照亮多边形的所有外部边界。她请你计算最少需要多少个照明装置，并给出一个可行的方案。

输入包含多组测试数据，第一行包含一个整数 $T$（$1 \le T \le 100$），表示测试数据的组数。 对于每组测试数据，第一行包含两个整数 $n$（$3 \le n \le 1000$）和 $m$（$1 \le m \le 1000$）。 接下来的 $n$ 行，每行用两个整数 $x$ 和 $y$（$|x|, |y| \le 10^9$）描述凸多边形上的一个顶点，即该顶点的笛卡尔坐标。所有顶点按逆时针顺序给出，且任意三点不共线。 再接下来的 $m$ 行，包含多边形外部的 $m$ 个不同的点，描述所有安装照明装置的合法位置。每行包含两个整数 $x$ 和 $y$（$|x|, |y| \le 10^9$），表示一个合法位置的笛卡尔坐标。这些位置从 $1$ 到 $m$ 编号。所有这些位置均不会落在多边形任意一条边的延长线上。

对于每组测试数据，如果不可能照亮多边形的所有外部边界，则输出一行一个整数 $-1$。否则，输出两行。第一行输出一个整数 $k$，表示 Rikka 照亮所有边界所需的最少照明装置数量。接着第二行输出 $k$ 个空格分隔的不同整数，描述一个可行方案，其中每个整数为所选位置的编号。 所有可行的方案均被接受，因此你可以输出其中任意一种。

翻译由 DeepSeek V4 Pro 完成