Shawarma Tent

题意翻译

#### 题目描述 首都柏林的地图可以看成一个坐标无限的平面。每一个坐标为整数的点有一个建筑物，每个建筑物都有连接到四个相邻建筑物的街道。所有街道都与坐标轴平行。 首都的主要学校位于 $(s_x,s_y)$。这所学校有 $n$ 名学生，第$i$名学生住在位于 $(x_i,y_i)$ 的房子里。有些学生可能住在同一所房子里，但没有学生住在 $(s_x,s_y)$。 下课后，每名学生沿着一条最短路径从学校走回家。所以第$i$个学生从学校到家的距离是 $|s_x-x_i|+|s_y-y_i|$。 柏林的供应部决定在首都某处（在某个坐标为整数的节点上）放置一个 shawarma 帐篷。如果从学校到第$i$名学生家的最短路径中至少有一条经过 shawarma 帐篷所在地，则认为第 $i$ 名学生将购买 shawarma 帐篷。学校所在地禁止放置 shawarma 帐篷，但 shawarma 帐篷可能与某名学生（甚至多名学生）的房屋在同一个坐标。 你想要找到购买 shawarma 帐篷的学生的最大可能数量以及此时帐篷的位置。 #### 输入格式 第一行包括三个整数 $n,s_x,s_y(1\leq n\leq 200000$，$0\leq s_x,s_y\leq 10^9)$——学生人数和学校坐标。 接下来有 $n$ 行。其中第 $i$ 行包含两个整数 $x_i,y_i$（$0\leq x_i,y_i\leq 10^9$）——第 $i$ 个学生住的房子的位置。某些房子的位置可能会重合，但没有学生住在和学校一样的位置。 #### 输出格式 输出应该由两行组成。第一行应该包含一个整数$c$——购买 shawarma 帐篷的学生的最大可能数量。 第二行应该包含两个整数 $p_x$ 和 $p_y$——帐篷所在的坐标。如果有多个答案，请输出其中的任何一个。请注意，每个 $p_x$ 和 $p_y$ 应不小于 $0$ 且不大于 $10^9$。 #### 说明/提示 在第一个样例中，如果我们在 $(4,2)$ 放置 shawarma 帐篷，那么住在 $(4,2),(4,1)$ 和 $(5,1)$ 的学生将会购买它。 在第二个样例中，可以在 $(1,1)$ 放置 shawarma 帐篷，那么住在 $(0,0)$ 的两个学生将会购买它。

题目描述

The map of the capital of Berland can be viewed on the infinite coordinate plane. Each point with integer coordinates contains a building, and there are streets connecting every building to four neighbouring buildings. All streets are parallel to the coordinate axes. The main school of the capital is located in $ (s_x, s_y) $ . There are $ n $ students attending this school, the $ i $ -th of them lives in the house located in $ (x_i, y_i) $ . It is possible that some students live in the same house, but no student lives in $ (s_x, s_y) $ . After classes end, each student walks from the school to his house along one of the shortest paths. So the distance the $ i $ -th student goes from the school to his house is $ |s_x - x_i| + |s_y - y_i| $ . The Provision Department of Berland has decided to open a shawarma tent somewhere in the capital (at some point with integer coordinates). It is considered that the $ i $ -th student will buy a shawarma if at least one of the shortest paths from the school to the $ i $ -th student's house goes through the point where the shawarma tent is located. It is forbidden to place the shawarma tent at the point where the school is located, but the coordinates of the shawarma tent may coincide with the coordinates of the house of some student (or even multiple students). You want to find the maximum possible number of students buying shawarma and the optimal location for the tent itself.

输入输出格式

输入格式

The first line contains three integers $ n $ , $ s_x $ , $ s_y $ ( $ 1 \le n \le 200\,000 $ , $ 0 \le s_x, s_y \le 10^{9} $ ) — the number of students and the coordinates of the school, respectively. Then $ n $ lines follow. The $ i $ -th of them contains two integers $ x_i $ , $ y_i $ ( $ 0 \le x_i, y_i \le 10^{9} $ ) — the location of the house where the $ i $ -th student lives. Some locations of houses may coincide, but no student lives in the same location where the school is situated.

输出格式

The output should consist of two lines. The first of them should contain one integer $ c $ — the maximum number of students that will buy shawarmas at the tent. The second line should contain two integers $ p_x $ and $ p_y $ — the coordinates where the tent should be located. If there are multiple answers, print any of them. Note that each of $ p_x $ and $ p_y $ should be not less than $ 0 $ and not greater than $ 10^{9} $ .

输入输出样例

输入样例 #1

4 3 2
1 3
4 2
5 1
4 1

输出样例 #1

3
4 2

输入样例 #2

3 100 100
0 0
0 0
100 200

输出样例 #2

2
99 100

输入样例 #3

7 10 12
5 6
20 23
15 4
16 5
4 54
12 1
4 15

输出样例 #3

4
10 11

说明

In the first example, If we build the shawarma tent in $ (4, 2) $ , then the students living in $ (4, 2) $ , $ (4, 1) $ and $ (5, 1) $ will visit it. In the second example, it is possible to build the shawarma tent in $ (1, 1) $ , then both students living in $ (0, 0) $ will visit it.