题目译自 ROI 2017 Day 1 T3. Тигры
~~本题的数据是 HeRaNO 配的,有锅请找他~~
在平面上有 $q$ 头虎,分别编号为 $1\ldots q$。每头虎身上有个信号发生器。
平面上有 $n$ 个信号接收器,第 $i$ 个接收器位于 $(x_i, y_i)$。
现在你要定位这 $q$ 头虎。你必须按照虎的编号依次定位,也就是说,你先得定位 $i$ 号虎,才能定位 $i+1$ 号虎。
定位一头虎可以进行 $\le k$ 次查询,每次查询可以选择不超过 $m$ 个接收器围成一个凸多边形(这 $m$ 个接收器是凸多边形的顶点)。检测系统会回答正在被定位的虎是否在这个凸多边形内。
如果有不超过 $m$ 个接收器围成一个凸多边形(这 $m$ 个接收器是凸多边形的顶点),凸多边形中没有其他接收器,且第 $i$ 只虎位于凸多边形中,那么这只虎就被定位完成。
请编写一个程序与检测系统交互,来依次定位每头虎。
交互形式
你可以编写一个函数 findTiger() 并在程序开始包含 grader.h 来完成交互过程。该函数无返回值,也没有参数。或者直接编写一个完整程序来进行交互。
你需要先从标准输出流中获得一个整数 $n$,表示信号接收器的个数。然后获得 $n$ 个坐标 $(x_i,y_i)$,表示接收器的位置。最后,你需要获得 $q$,即需要定位虎的数量。
你可以向标准输出中输出询问和回答,形式如下:
- 对于询问一头虎是否在一个凸多边形内,你需要先输出一个字符 ?,后跟一个整数 $m(3\le m\le n)$,表示查询的接收器数量,后跟 $m$ 个整数 $p_i(1\le p_i\le n)$,按逆时针顺序输出接收器的编号,字符,整数之间用一个空格隔开。如果一头虎在查询的范围内,交互器会向标准输出中输出 $\texttt{Yes}$,否则会输出 $\texttt{No}$;
- 对于回答一头虎的位置,你需要先输出一个字符 !,后跟一个整数 $m(3\le m\le n)$,表示这头虎在又 $m$ 个接收器围成的凸多边形的范围内,后跟 $m$ 个整数 $p_i(1\le p_i\le n)$,按逆时针顺序输出接收器编号,要求围成的范围内没有接收器且只有一头虎。字符,整数之间用一个空格隔开。
你需要按顺序寻找每头虎的位置。保证虎的位置在交互过程中不会改变,如果有多个凸多边形可以确定虎的位置,你可以回答任意一个。
下图展示了一个确定虎的位置的过程。
