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