Square or rectangle#186

Square or rectangle (Editorial)

Ключ до задачі — обмеження на площу: зафарбована ділянка займає не менше $4%$ дошки, тобто щонайменше $400$ клітинок. Звідси випливає, що сторона квадрата не менша за $20$ : квадрат площею $\geq 400$ має сторону $\geq 20$ .

Крок 1: сітка запитів. Запитаємо всі $25$ точок з координатами з множини ${20, 40, 60, 80, 100}$ \{20, 40, 60, 80, 100\} по обох осях.

Чому цього достатньо? Кратні двадцяти йдуть рівно через $20$ , тому будь-які $20$ послідовних чисел з відрізка $[1, 100]$ містять рівно одне з чисел $20, 40, 60, 80, 100$ 20, 40, 60, 80, 100. Якщо фігура — квадрат зі стороною $\geq 20$ , то і його діапазон рядків, і діапазон стовпців містять по такому числу, отже відповідна точка сітки гарантовано лежить усередині.

Тому якщо жоден із $25$ запитів не потрапив усередину, то хоча б одна сторона фігури менша за $20$ . Але тоді це точно не квадрат (інакше площа була б меншою за $400$ ) — одразу відповідаємо rectangle.

Крок 2: знайти лівий верхній кут. Нехай перша (у порядку обходу: спочатку за зростанням $x$ , потім за зростанням $y$ ) точка-влучання — це $(a, b)$ . Тоді $x_{1} \geq a - 19$ x_1 \ge a - 19: інакше точка $(a - 20, b)$ (a - 20, b) теж була б усередині, а вона йде раніше в порядку обходу.

Отже, $x_{1}$ x_1 шукаємо двійковим пошуком на відрізку $[a - 19, a]$ [a-19,\, a]: предикат « $(x, b)$ всередині» монотонний, бо для $x \leq a$ x \le a точка всередині тоді й лише тоді, коли $x \geq x_{1}$ x \ge x_1. Аналогічно знаходимо $y_{1}$ y_1 на відрізку $[b - 19, b]$ [b-19,\, b], запитуючи точки $(a, y)$ .

Крок 3: знайти меншу сторону. Ідемо по діагоналі з кута: точка $(x_{1} + m, y_{1} + m)$ (x_1 + m,\; y_1 + m) лежить усередині тоді й лише тоді, коли $m \leq x_{2} - x_{1}$ m \le x_2 - x_1 і $m \leq y_{2} - y_{1}$ m \le y_2 - y_1. Предикат знову монотонний, тому двійковим пошуком знаходимо найбільше таке $m$ ; позначимо його $d$ . За побудовою

d = min (x_{2} - x_{1}, y_{2} - y_{1}) .

d = \min(x_2 - x_1,\; y_2 - y_1).

Крок 4: відповідь. Фігура є квадратом тоді й лише тоді, коли обидві сторони дорівнюють $d$ , тобто коли жоден із двох «сусідів за кутом» не належить фігурі:

(x_{1} + d + 1, y_{1} + d) та (x_{1} + d, y_{1} + d + 1)

(x_1 + d + 1,\; y_1 + d) \quad \text{та} \quad (x_1 + d,\; y_1 + d + 1)

— обидві точки мають бути outside. Якщо хоч одна всередині, відповідна сторона довша, і це прямокутник.

Разом виходить близько $25 + 5 + 5 + 7 + 2 \approx 44$ 25 + 5 + 5 + 7 + 2 \approx 44 запити — з величезним запасом до ліміту $10000$ .

Не забувайте робити flush після кожного запиту, інакше програма зависне в очікуванні відповіді.