题目描述

Rikka loves convex polygons, so she decides to install some illuminants to embellish polygons.

Now she has a large convex polygon with $n$ sides. She also has $m$ different points strictly outside the polygon which are all legal positions to install illuminants.

An illuminant can light up some exterior boundaries of the polygon.

Rikka wants to install some illuminants to light up all exterior boundaries of the polygon. She asks you to calculate the least number of illuminants which she needs and provide a feasible scheme.

输入格式

The input contains several test cases, and the first line contains a single integer $T$ ($1≤T≤100$), the number of test cases.

For each test case, the first line contains two integers $n$ ($3≤n≤1000$) and $m$ ($1≤m≤1000$).

Each of the following $n$ lines describes a vertex on the convex polygon with two integers $x$ and $y$ ($|x|,|y|≤10^9$$), the Cartesian coordinates of the vertex. All these vertices are given in counter-clockwise order and any three of them are not collinear.

Then the following mm lines contain mm different points outside the polygon describing all legal positions to install illuminants. Each of them contains two integers $x$ and $y$ ($|x|,|y|≤10^9$), the Cartesian coordinates of a legal position. They are numbered from $1$ to $m$. All these positions would not lie in some extension lines for the sides of the polygon.

输出格式

For each test case, if it's impossible to light up all exterior boundaries of the polygon, output a single line with a single integer $−1$. Otherwise, output two lines. Firstly, output a line with a single integer $k$, representing the least number of illuminants Rikka needs to light up all the boundaries. Then, output a line with $k$ space-separated distinct integers, describing a feasible scheme, each of which is the index of a selected position.

1
3 3
0 0
1 0
0 1
-1 -1
3 -1
-1 3

2
2 1

题目大意

给定一个 $n$ 个点的凸包(这 $n$ 个点满足逆时针给出，同时所有点互不相同，且不存在三个点在同一条直线上)，再给出 $m$ 个光照点，每个光照点的照射范围为 $360$ 度，光照不会穿过凸包，问最少选取几个光照点可以照亮整个凸包，要求输出方案，保证不会出现一个光照点位于凸包的延长线上。

题目来源

2018-ICPC国际大学生程序设计竞赛-徐州站 - M题