E. Пустой треугольник
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это интерактивная задача.

Розовые солдаты спрятали от вас $$$n$$$ ($$$3 \le n \le 1500$$$) фиксированных точек $$$(x_1,y_1), (x_2,y_2), \ldots, (x_n,y_n)$$$, координаты которых вам не даны. Также известно, что ни две точки не имеют одинаковых координат, и ни три точки не лежат на одной прямой.

Вы можете спросить у Фронтмена о трех различных индексах $$$i$$$, $$$j$$$, $$$k$$$. Затем он рисует треугольник с вершинами $$$(x_i,y_i)$$$, $$$(x_j,y_j)$$$, $$$(x_k,y_k)$$$ и отвечает следующим образом:

  • Если хотя бы одна из скрытых точек лежит внутри треугольника, то Фронтмен дает вам индекс одной из таких точек. Обратите внимание, что если таких точек несколько, Фронтмен может произвольно выбрать одну из них.
  • В противном случае Фронтмен отвечает $$$0$$$.
Ваша задача в этой задаче — найти треугольник, не содержащий никаких других скрытых точек, такой как синий на диаграмме.

Используя не более чем $$$\mathbf{75}$$$ запросов, вы должны найти любой треугольник, образованный тремя из точек, не содержащий никаких других скрытых точек внутри.

Обратите внимание, что Фронтмен может быть адаптивным при выборе точки, которую он вам дает. Другими словами, выбор точки может определяться различными факторами, включая, но не ограничиваясь, ориентацией точек и предыдущими запросами. Однако следует отметить, что последовательность точек никогда не будет изменена.

В этой задаче взломы отключены. Ваше решение будет оцениваться по ровно $$$\mathbf{35}$$$ тестам, включая пример входных данных.

Протокол взаимодействия

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 20$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора содержит одно положительное целое число $$$n$$$ — количество точек ($$$3 \le n \le 1500$$$).

После этого вы можете вывести следующее на отдельной строке, чтобы задать запрос:

  • «? i j k» ($$$1 \le i,j,k \le n$$$, $$$i \ne j$$$, $$$i \ne k$$$, $$$j \ne k$$$): Спросите о треугольнике, образованном $$$(x_i,y_i)$$$, $$$(x_j,y_j)$$$, $$$(x_k,y_k)$$$.

Затем интерактор отвечает одним целым числом на новой строке:

  • Если ваш запрос некорректный или количество запросов превысило $$$\mathbf{75}$$$, то интерактор отвечает $$$-1$$$;
  • Если существует индекс $$$p$$$ ($$$1 \le p \le n$$$), такой что точка $$$(x_p,y_p)$$$ находится внутри треугольника, то любой такой индекс $$$p$$$ будет дан;
  • В противном случае интерактор отвечает $$$0$$$.

Если вы хотите напечатать ответ, вы можете вывести следующее на отдельной строке:

  • «! i j k» ($$$1 \le i,j,k \le n$$$, $$$i \ne j$$$, $$$i \ne k$$$, $$$j \ne k$$$): Треугольник, образованный $$$(x_i,y_i)$$$, $$$(x_j,y_j)$$$, $$$(x_k,y_k)$$$, не содержит никаких других скрытых точек.

Затем происходит следующее взаимодействие:

  • Если ответ недействителен или треугольник содержит другую скрытую точку, интерактор отвечает $$$-1$$$;
  • Если ответ правильный и есть еще тестовые случаи для решения, вам будет дано значение $$$n$$$ для следующего теста;
  • В противном случае это означает, что все тестовые случаи решены правильно, и ваша программа может завершиться корректно.

Обратите внимание, что печать ответа не учитывается в количестве сделанных запросов.

Обратите внимание, что интерактор может быть адаптивным при выборе точки, которую он вам дает. Другими словами, выбор точки может определяться различными факторами, включая, но не ограничиваясь, ориентацией точек и предыдущими запросами. Однако следует отметить, что последовательность точек никогда не будет изменена.

После вывода каждого запроса не забудьте вывести перевод строки и сбросить буфер вывода$$$^{\text{∗}}$$$. В противном случае вы получите вердикт Решение «зависло».

На любом шаге взаимодействия, если вы считали $$$-1$$$ вместо корректных данных, ваше решение должно немедленно завершиться. Это означает, что ваше решение получит вердикт Неправильный ответ из-за некорректного запроса или любой другой ошибки. Если программа не завершится, вы можете получить любой вердикт, так как ваша программа продолжит чтение из закрытого потока.

Взломы

В этой задаче взломы отключены. Ваше решение будет оцениваться по ровно $$$\mathbf{35}$$$ тестам, включая пример входных данных.

$$$^{\text{∗}}$$$Чтобы сбросить буфер вывода, используйте:

  • fflush(stdout) или cout.flush() в C++;
  • sys.stdout.flush() в Python;
  • смотрите документацию для других языков.
Пример
Входные данные
2
6

5

4

0

3
Выходные данные


? 1 2 3

? 1 5 3

? 2 5 6

! 2 5 6

! 1 2 3
Примечание

В первом примере точки: $$$(3,0),(0,3),(5,2),(3,1),(2,2),(4,4)$$$.

Треугольники, соответствующие трем запросам, следующие.

Вы можете видеть, что треугольник, образованный $$$(0,3)$$$, $$$(2,2)$$$, $$$(4,4)$$$, не содержит никаких других скрытых точек внутри. Поэтому это правильный ответ.

Обратите внимание, что пример взаимодействия показывает только допустимое взаимодействие, и не обязательно фактический ответ. Например, возможно, что Фронтмен отвечает $$$4$$$, когда вы запрашиваете «? 1 2 3». Однако, поскольку Фронтмен не изменяет последовательность точек, он никогда не отвечает $$$6$$$ на тот же запрос.

Во втором примере всего $$$3$$$ точки. Поэтому мы знаем, что уникальный треугольник, образованный точками, не содержит никаких других скрытых точек внутри.