loj#P2768. 「ROI 2017 Day 1」虎

「ROI 2017 Day 1」虎

题目描述

题目译自 ROI 2017 Day 1 T3. Тигры

本题的数据是 HeRaNO 配的,有锅请找他

在平面上有 qq 头虎,分别编号为 1q1\ldots q。每头虎身上有个信号发生器。
平面上有 nn 个信号接收器,第 ii 个接收器位于 (xi,yi)(x_i, y_i)
现在你要定位这 qq 头虎。你必须按照虎的编号依次定位,也就是说,你先得定位 ii 号虎,才能定位 i+1i+1 号虎。
定位一头虎可以进行 k\le k 次查询,每次查询可以选择不超过 mm 个接收器围成一个凸多边形(这 mm 个接收器是凸多边形的顶点)。检测系统会回答正在被定位的虎是否在这个凸多边形内。
如果有不超过 mm 个接收器围成一个凸多边形(这 mm 个接收器是凸多边形的顶点),凸多边形中没有其他接收器,且第 ii 只虎位于凸多边形中,那么这只虎就被定位完成。
请编写一个程序与检测系统交互,来依次定位每头虎。

交互形式

你可以编写一个函数 findTiger() 并在程序开始包含 grader.h 来完成交互过程。该函数无返回值,也没有参数。或者直接编写一个完整程序来进行交互。

你需要先从标准输出流中获得一个整数 nn,表示信号接收器的个数。然后获得 nn 个坐标 (xi,yi)(x_i,y_i),表示接收器的位置。最后,你需要获得 qq,即需要定位虎的数量。

你可以向标准输出中输出询问和回答,形式如下:

  • 对于询问一头虎是否在一个凸多边形内,你需要先输出一个字符 ?,后跟一个整数 m(3mn)m(3\le m\le n),表示查询的接收器数量,后跟 mm 个整数 pi(1pin)p_i(1\le p_i\le n),按逆时针顺序输出接收器的编号,字符,整数之间用一个空格隔开。如果一头虎在查询的范围内,交互器会向标准输出中输出 Yes\texttt{Yes},否则会输出 No\texttt{No}
  • 对于回答一头虎的位置,你需要先输出一个字符 !,后跟一个整数 m(3mn)m(3\le m\le n),表示这头虎在又 mm 个接收器围成的凸多边形的范围内,后跟 mm 个整数 pi(1pin)p_i(1\le p_i\le n),按逆时针顺序输出接收器编号,要求围成的范围内没有接收器且只有一头虎。字符,整数之间用一个空格隔开。

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

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

tiger.png

数据范围与提示

子任务编号 分值 nn qq kk
11 1515 3n63\le n\le 6 1q501\le q\le 50 k=4000k=4000
22 1717 3n203\le n\le 20
33 99 3n603\le n\le 60 1q4001\le q\le 400
44 99 3n3003\le n\le 300 1q10001\le q\le 1000 k=600k=600
55 1010 3n50003\le n\le 5000 1q101\le q\le 10 k=10000k=10000
66 1010 3n3003\le n\le 300 1q10001\le q\le 1000 k=250k=250
77 1010 3n10003\le n\le 1000 k=200k=200
88 1010 1q20001\le q\le 2000 k=60k=60
99 1010 3n25003\le n\le 2500 k=40k=40