Прямокутник і точки#12952

Прямокутник і точки (Editorial)

Розглянемо мінімальну відповідь, якщо лівий нижній кут зсувається вгору та вправо. 3 інші випадки розв’язуються так само, за допомогою віддзеркалення точок.

Посортуємо всі точки по , а при рівності по . Йтимемо зліва направо, розглянемо точку p_i, яка має максимальну координату серед всіх точок на суфіксі. Знайдемо такий найправіший індекс , що p_j.x \le p_i.x і p_j.y \geq p_i.y. Тоді якщо перемістити прямокутник так, що його лівий нижній кут був у точці (p_j.x, p_i.y), то всі точки опиняться на межах або поза межами прямокутника. Назвемо таку точку (p_j.x, p_i.y) цікавою.

Цікаві точки можна легко знаходити за допомогою стека, де завжди виконується, що остання точка є найправішою та нийнижчою серед усіх у стеці, а якщо ми намагаємося додати точку, яка суперечить цьому, видалятимемо зі стека останню точку, поки умова не виконуватиметься. Порахуємо відповідь для всіх цікавих точок та виберемо мінімальну.