P10651 [ROI 2017] Tiger (Collecting Interactive Library) (Day 1)

## Statement On a plane, there are $q$ signal transmitters and $n$ signal receivers. You know the position of each signal receiver, but you do not know the positions of the signal transmitters. You want to locate the positions of the signal transmitters numbered $1 \sim q$ **in order**. For each transmitter, you may use the following method at most $k$ times to obtain some information through the receivers: - Choose $m \ge 3$ receivers. The system will return whether the convex hull formed by connecting these $m$ receivers in the given order contains the signal transmitter. After you have determined the position of the currently numbered signal transmitter, you must output to the interactive library a confirmation plan using the following operation: - Choose $m \ge 3$ receivers such that the convex hull formed by these receivers contains **no other receivers strictly inside**, and the transmitter whose position you are currently confirming lies inside the convex hull. It is guaranteed that no three signal receivers are collinear, no signal transmitter lies on a line passing through two signal receivers, and each signal transmitter has at least one valid confirmation plan. ## Interaction Process You can write a function `findTiger()` and include `grader.h` at the start of the program to complete the interaction. This function has no return value and no parameters. Alternatively, you may write a complete program to perform the interaction directly. You first need to read an integer $n$ from the standard input stream, which denotes the number of signal receivers. Then read $n$ coordinates $(x_i, y_i)$, which denote the positions of the receivers. Finally, read $q$, i.e., the number of signal transmitters that need to be located. You can output queries and answers to standard output in the following forms: - To query whether a signal transmitter lies inside a convex polygon, you should first output a character `?`, followed by an integer $m(3 \le m \le n)$ indicating the number of receivers in the query, followed by $m$ integers $p_i(1 \le p_i \le n)$, the indices of the receivers in counterclockwise order. Separate the character and integers by one space. If the current signal transmitter lies inside the queried region, the interactor will output $\texttt{Yes}$ to standard input; otherwise it will output $\texttt{No}$; - To answer (confirm) the position of a signal transmitter, you should first output a character `!`, followed by an integer $m(3 \le m \le n)$ indicating that this signal transmitter lies within the convex polygon formed by $m$ receivers, followed by $m$ integers $p_i(1 \le p_i \le n)$, the receiver indices in counterclockwise order. The region must contain no receivers inside and must contain the current signal transmitter. Separate the character and integers by one space. You must find each signal transmitter in order. It is guaranteed that the signal receiver positions will not change during the interaction. If multiple convex polygons can confirm the position of a signal transmitter, you may output any one of them.

N/A

# Hint #

## Hint The following shows an example of an interaction process:  ## Constraints Note: This problem lacks the interactive library. For the complete testdata, please go to [LOJ P2768](https://loj.ac/p/2768) for judging. |Subtask ID|Score|$3 \le n \le$|$1 \le q \le$|$k =$| |:-----------:|:-----------:|:-----------:|:-----------:|:-----------:| |$1$|$15$|$6$|$50$|$4000$| |$2$|$17$|$20$|$50$|$4000$| |$3$|$9$|$60$|$400$|$4000$| |$4$|$9$|$300$|$1000$|$600$| |$5$|$10$|$5000$|$10$|$10000$| |$6$|$10$|$300$|$1000$|$250$| |$7$|$10$|$1000$|$1000$|$200$| |$8$|$10$|$1000$|$2000$|$60$| |$9$|$10$|$2500$|$2000$|$40$| Translated by ChatGPT 5