| Codeforces Round 371 (Div. 1) |
|---|
| Закончено |
На уроке математики ёжик Филя изучал новую геометрическую фигуру — прямоугольник. Ему дали задание: нарисовать на квадратном клетчатом поле, состоящем из n × n единичных квадратиков, два прямоугольника, стороны которых параллельны осям координат, при этом каждый квадратик либо полностью принадлежит прямоугольнику, либо полностью не принадлежит. Строки поля пронумерованы снизу вверх от 1 до n, столбцы пронумерованы слева направо от 1 до n. Клетка, расположенная на пересечении строки r и столбца c, обозначается (r, c). Филя нарисовал два прямоугольника так, что никакая клетка не принадлежит сразу обоим прямоугольникам.
Через некоторое время ёжику стало интересно, в каких координатах были расположены его прямоугольники, но он никак не мог найти, где он их нарисовал. Как оказалось, рисунки были у совы Сони. Так как Соня достаточно вредная, она решила сыграть с Филей в игру. Он должен спрашивать, сколько прямоугольников находятся полностью внутри некоторого прямоугольника-запроса, а Соня будет отвечать на его вопросы. Прямоугольник-запрос удовлетворяет тем же ограничениям, что и прямоугольники, нарисованные Филей. Прямоугольник полностью лежит внутри прямоугольника-запроса, если каждая его клетка является клеткой прямоугольника-запроса.
Поскольку Филя хорошо знает Соню, он уверен, что если он спросит её более 200 раз, то сове надоест, и он больше не сможет получать ответы.
В первой строке записано целое число n (2 ≤ n ≤ 216) — размеры квадратного поля.
Ответом на каждый запрос является число от 0 до 2 — количество прямоугольников, которые полностью находятся в прямоугольнике-запросе.
Чтобы сделать запрос, вы должны вывести «? x1 y1 x2 y2» (без кавычек) (1 ≤ x1 ≤ x2 ≤ n, 1 ≤ y1 ≤ y2 ≤ n), где (x1, y1) — координаты левой нижней клетки прямоугольника-запроса, а (x2, y2) — координаты правой верхней клетки прямоугольника-запроса. Разрешается выполнить не более 200 запросов. После каждого запроса нужно вывести перевод строки и сделать операцию «flush», после чего считать ответ Сони.
В момент, когда вы считаете, что уже знаете ответ (или у вас кончились запросы), необходимо вывести «! x11 y11 x12 y12 x21 y21 x22 y22» (без кавычек), где первые четыре числа описывают левую нижнюю и правую верхнюю клетки первого прямоугольника, а следующие четыре — второго. Прямоугольники можно выводить в произвольном порядке. После ответа нужно вывести перевод строки и сделать операцию 'flush'. После вывода ответа ваша программа должна завершиться.
Чтобы сделать операцию 'flush' сразу после вывода числа и перевода строки нужно сделать:
cout.flush() или fflush(stdout) в C++;
System.out.flush() в Java;
stdout.flush() в Python;
flush(output) в Pascal;
смотрите документацию для других языков.
Вы получите Wrong Answer, если сделаете более 200 запросов или если не угадаете координаты прямоугольников.
Вы получите вердикт Idleness Limit Exceeded, если не будете ничего выводить (а тестирующая программа будет ожидать ввода) или забудете сделать операцию 'flush' после какого-нибудь вывода.
Описание теста для взлома
В первой строке теста должно быть записано число n (2 ≤ n ≤ 216).
Во второй строке должно быть четыре числа x1, y1, x2, y2 (1 ≤ x1 ≤ x2 ≤ n, 1 ≤ y1 ≤ y2 ≤ n) — описание первого прямоугольника.
В третьей строке должно быть описание второго прямоугольника в аналогичном формате.
5
2
1
0
1
1
1
0
1
? 1 1 5 5
? 1 1 3 3
? 1 1 3 1
? 2 2 2 2
? 3 3 5 5
? 3 3 3 5
? 3 3 3 4
? 3 4 3 5
! 2 2 2 2 3 4 3 5
