Задача B. Точка на карте
Задачу добавил: alef
Успешно сдано решений: 306
Ещё один важный вопрос, который предстоит решить устроителям чемпионата — где разместить стадион.
Город S на карте выглядит как прямоугольник, левый нижний угол которого расположен в точке с координатами (0, 0), а правый верхний — в точке с координатами (a, b).
Мэр города S полагает, что если разместить стадион в некоторой точке с координатами (x, y), это приведёт к развитию территории в квадрате с центром в этой точке и стороной 2·d. Стороны этого квадрата будут параллельны сторонам прямоугольника, описывающего город.
Мэру предложили n проектов размещения стадиона.
С точки зрения мэра городская территория достаточно развита, так что он заинтересован в том, чтобы развитие получила как можно большая по площади территория, не относящаяся к городу. При этом он хочет, чтобы развиваемая территория имела хотя бы одну общую точку с городом.
Ваша задача — определить, какой проект следует выбрать мэру. Гарантируется, что среди предложенных проектов существует хотя бы один подходящий.
В первой строке содержатся целые числа a, b, n, d (1 ≤ a, b ≤ 105, 1 ≤ n ≤ 105, 1 ≤ d ≤ 105) — координаты правого верхнего угла города, количество проектов размещения стадиона, половина длины стороны квадрата, территория в котором получает развитие.
Далее следуют n строк. В строке #i содержится пара чисел xi, yi ( - 3·105 ≤ xi, yi ≤ 3·105) через пробел — координаты точки, в которой проект #i предлагает разместить стадион.
В первой строке выведите два целых числа через пробел: номер проекта, который следует выбрать мэру, и площадь территории, которая получит развитие.
Если существует несколько вариантов ответа, выведите любой из них.
Подзадача 1 (до 20 баллов)
2 ≤ a ≤ 1000, 1 ≤ b ≤ 1000, 1 ≤ n ≤ 100, d ≤ xi ≤ (a - d), a ≥ 2·d, - 3000 ≤ yi ≤ 3000
Подзадача 2 (до 80 баллов)
Все величины из условия могут принимать любые допустимые значения.
В обеих подзадачах баллы начисляются за каждый пройденный тест.
По запросу сообщается результат проверки на каждом тесте.
Обратите внимание: второй пример не удовлетворяет условиям подзадачи 1. Напомним, что решение участника должно выдавать верные ответы на все тесты из условия, даже если оно корректно решает только первую подзадачу.
10 12 4 3
4 11
7 5
6 -2
5 1
3 30
10 12 4 3
2 14
13 15
-2 -4
13 -2
4 36
Поясним приведённые примеры.
Номера квадратов на рисунках соответствуют номерам их центров в тестовых примерах.
Первому примеру соответствует рис. 1.
Рис.1 Как можно видеть, квадрат под номером #2 полностью находится внутри прямоугольника, очерчивающего город, и охваченная им площадь не получит развития (с точки зрения мэра). Квадраты #1 и #4 позволят развить территории площадью 12 единиц каждая. А вот квадрат #3 даст возможность развить территорию площадью 30 единиц, и именно его номер и эту площадь следует вывести в качестве ответа.
Второй пример проиллюстрирован рисунком 2.
Рис.2 И квадрат #2, и квадрат #4 имеют общие точки с прямоугольником, очерчивающим город. При этом они позволяют развить территорию максимально возможной площади 36 единиц, так что любой из них может быть выбран в качестве правильного ответа (т.е. в примере корректен не только вывод 4 36, но и 2 36). А вот вывод 3 36 будет неправильным: квадрат #3 не имеет ни одной общей точки с городом.
И ещё один пример:
10 12 4 3
2 11
13 15
-2 -4
11 -2
Рис.3 Единственно возможным ответом будет номер 2; номер 3 ответом быть не может, поскольку квадрат #3, в отличие от квадрата #2, не имеет ни одной общей точки с прямоугольником, очерчивающим город.