printРабочее место участника

printЗадачи

69. Поле для крикета

Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Жил-был жадный Король. Он приказал своему главному Архитектору построить поле для королевского крикета в парке. Король был таким жадным, что не послушал предложение своего Архитектора построить поле прямо в центре парка и окружить его живописным бордюром деревьев, специально посаженных вокруг. Вместо этого он приказал не срубать деревья и не сажать новых, но построить самое большое поле для крикета, какое только можно. Если Король обнаружит, что Архитектор посмел тронуть даже единственное дерево в парке или спроектировал меньшее поле, чем было возможно, Архитектор лишится головы. Более того, он потребовал от Архитектора представить план поля, где указаны его точное положение и размер.
1482.gif
Ваша задача – помочь бедному Архитектору сохранить голову, написав программу, которая найдёт максимальный размер поля для крикета и его положение внутри парка, удовлетворяющие требованиям Короля.
Задача слегка упрощена тем, что парк Короля имеет прямоугольную форму и расположен на плоской поверхности. Более того, границы парка параллельны направлениям север – юг и восток – запад. В то же время игра в королевский крикет всегда происходит на квадратном поле, границы которого также параллельны направлениям север – юг и восток – запад. Архитектор уже сопоставил парку прямоугольную декартову систему координат и точно определил координаты каждого дерева. Оси этой системы координат, конечно, параллельны направлениям север – юг и восток – запад. Юго-западный угол парка имеет координаты (0, 0), а северо-восточный – координаты (`W`, `H`), где `W` и `H` – длина и ширина парка соответственно.
В этой задаче вы можете пренебречь диаметром деревьев. Деревья не могут находиться внутри поля для крикета, но могут располагаться на его сторонах. Поле для крикета может также касаться границы парка, но не должно лежать вне парка.
Ввод
Первая строка содержит три целых числа `N`, `W` и `H`, разделённых пробелами: `N` – число деревьев в парке, `W` и `H` – длина и ширина парка соответственно.
Следующие `N` строк описывают координаты деревьев в парке. Каждая строка содержит два целых числа `x_i` и `y_i`, разделённых пробелом и представляющих собой координаты `i`-го дерева. Все деревья имеют различные координаты.
Ограничения: `1\ ≤\ N\ ≤\ 100`, `1\ ≤\ W,\ H\ ≤\ 10\ 000`, `0\ ≤\ x_i\ ≤\ W`, `0\ ≤\ y_i\ ≤\ H`.
Вывод
Вывести через пробел три целых числа, `P`, `Q` и `L`, где (`P`, `Q`) – координаты юго-западного угла поля для крикета, `L` – длина его сторон. Если существует несколько возможных положений поля максимального размера, вывести любое.

Пример ввода 2

7 10 7
3 2
4 2
7 0
7 3
4 5
2 4
1 7

Пример вывода 2

4 3 4
Источник: NEERC, 2002
loading