28191번 - Random Interactive Convex Hull Bot 다국어인터랙티브

How do setters come up with problems? Sometimes they just take a couple of buzzwords and smash them together. But we are in 2023, so this totally can be outsourced to AI. Introducing our creation based on ChatGPT --- RICH B! And its first official problem:

Prompt: Random Interactive Convex Hull

Problem: A set of $n$ points is chosen uniformly at random among all sets of 2D points with positive integer coordinates up to $10^9$ of size $n$ so that no three points lie on the same line. Your task is to find their convex hull. But you are not given the points. Instead, you can make queries of the form "? $i$ $j$ $k$", and the jury program will respond to you with $1$ if the turn from $\overrightarrow{P_i P_j}$ to $\overrightarrow{P_i P_k}$ is counter-clockwise, and it will respond with $-1$ if the turn is clockwise. You can interpret it as $\mathbf{sgn} \left( \overrightarrow{P_i P_j} \times \overrightarrow{P_i P_k} \right)$, where $\times$ is cross product. When you think that you know the convex hull, print it as "! $k$ $i_1$ $i_2$ $\ldots$ $i_k$", where $k$ is the size of the convex hull and $i_1, i_2, \ldots, i_k$ are the indices of points on the convex hull in counter-clockwise order. Any point can be the first one. Constraints: $3 \le n \le 5000$ and you can make at most $30\,000$ queries.

Read $n$ ($3 \le n \le 5000$).

Then start asking queries by printing "? $i$ $j$ $k$" ($1 \le i, j, k \le n$, $\{i, j, k\}$ are distinct). After each query read the response, which is either $1$ or $-1$. You can make at most $30\,000$ queries.

Don't forget to flush the output, you are not a baby, you know how to do this. Don't do invalid queries, that might cause weird verdicts and you don't want that.

After making all the queries you want, print the answer as "! $k$ $i_1$ $i_2$ $\ldots$ $i_k$", where $k$ is the size of the convex hull and $i_1, i_2, \ldots, i_k$ are the indices of points on the convex hull in counter-clockwise order. This is not counted as a query.

It is guaranteed that the set of points is chosen uniformly at random among all sets of 2D points with positive integer coordinates up to $10^9$ of size $n$ such that no three points lie on the same line. The order of the points is also uniformly random. The interactor is not adaptive.