2768 「ROI 2017 Day 1」虎

内存限制:512 MB 时间限制:2000 ms

题目描述

题目译自 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)$,按逆时针顺序输出接收器编号,要求围成的范围内没有接收器且只有一头虎。字符,整数之间用一个空格隔开。

你需要按顺序寻找每头虎的位置。保证虎的位置在交互过程中不会改变,如果有多个凸多边形可以确定虎的位置,你可以回答任意一个。

下图展示了一个确定虎的位置的过程。

tiger.png

数据范围与提示

子任务编号 分值 $n$ $q$ $k$
$1$ $15$ $3\le n\le 6$ $1\le q\le 50$ $k=4000$
$2$ $17$ $3\le n\le 20$ $1\le q\le 50$ $k=4000$
$3$ $9$ $3\le n\le 60$ $1\le q\le 400$ $k=4000$
$4$ $9 $ $3\le n\le 300$ $1\le q\le 1000$ $k=600$
$5$ $10$ $3\le n\le 5000$ $1\le q\le 10$ $k=10000$
$6$ $10 $ $3\le n\le 300$ $1\le q\le 1000$ $k=250$
$7$ $10$ $3\le n\le 1000$ $1\le q\le 1000$ $k=200$
$8$ $10 $ $3\le n\le 1000$ $1\le q\le 2000$ $k=60$
$9$ $10$ $3\le n\le 2500$ $1\le q\le 2000$ $k=40$