Codeforces Round 608 (Div. 2) |
---|
Закончено |
План столицы Берляндии представляет собой плоскость, причем все строения расположены в точках с целочисленными координатами, а пешеходными улицами являются отрезки, соединяющие каждую точку с четырьмя соседними. Все пешеходные улицы параллельны осям координат.
Известно, что школа в столице Берляндии расположена в точке $$$(s_x, s_y)$$$. В школе учатся $$$n$$$ учеников, причем $$$i$$$-й ученик живет в доме, который расположен в точке $$$(x_i, y_i)$$$. Допустимо, что несколько учеников живут в одном и том же доме, но никакой ученик не живет в точке $$$(s_x, s_y)$$$.
После занятий каждый ученик идет из школы до своего дома по улицам, причем каждый ученик обязательно идет до своего дома по какому-то из кратчайших путей. Таким образом, расстояние, которое преодолеет $$$i$$$-й ученик, чтобы добраться из школы до дома, равно $$$|s_x - x_i| + |s_y - y_i|$$$.
Министерство питания решило установить ларек с шаурмой в столице Берляндии в точке с целочисленными координатами. Считается, что $$$i$$$-й школьник купит шаурму в ларьке, если ларек находится на одном из кратчайших путей $$$i$$$-го школьника до дома. Запрещено ставить ларек с шаурмой в той же точке, в которой расположена школа, но разрешено ставить ларек в той точке, в которой расположен дом кого-то из учеников.
Определите максимальное количество школьников, которые смогут купить шаурму в ларьке, а также сообщите координаты для постройки ларька.
В первой строке следует три целых числа $$$n$$$, $$$s_x$$$, $$$s_y$$$ ($$$1 \le n \le 200\,000$$$, $$$0 \le s_x, s_y \le 10^{9}$$$) — количество школьников и координаты школы.
В $$$i$$$-й из следующих $$$n$$$ строк следуют по два целых числа $$$x_i$$$, $$$y_i$$$ ($$$0 \le x_i, y_i \le 10^{9}$$$) — координаты дома $$$i$$$-го школьника. Координаты домов у некоторых школьников могут совпадать. Гарантируется, что дом никакого школьника не расположен в той же точке, что и школа.
В первую строку выведите целое число $$$c$$$ — максимальное количество школьников, которые смогут купить шаурму в ларьке.
Во вторую строку выведите два целых числа $$$p_x$$$ и $$$p_y$$$ — координаты для постройки ларька. Если подходящих ответов несколько, разрешается вывести любой из них. Обратите внимание, что каждое из чисел $$$p_x$$$ и $$$p_y$$$ должно быть не менее $$$0$$$ и не более $$$10^{9}$$$.
4 3 2 1 3 4 2 5 1 4 1
3 4 2
3 100 100 0 0 0 0 100 200
2 99 100
7 10 12 5 6 20 23 15 4 16 5 4 54 12 1 4 15
4 10 11
В первом примере нужно построить ларек с шаурмой в точке $$$(4, 2)$$$. Тогда три школьника его посетят. Это школьники, чьи дома расположены в точках $$$(4, 2)$$$, $$$(4, 1)$$$ и $$$(5, 1)$$$.
Во втором примере можно, например, построить ларек с шаурмой в точке $$$(1, 1)$$$. В таком случае оба школьника, дом которых расположен в точке $$$(0, 0)$$$, его посетят.
Название |
---|