CF1271C.Shawarma Tent
普及-
通过率:0%
时间限制:1.00s
内存限制:256MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
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 (sx,sy). There are n students attending this school, the i-th of them lives in the house located in (xi,yi). It is possible that some students live in the same house, but no student lives in (sx,sy).
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 ∣sx−xi∣+∣sy−yi∣.
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.
首都贝尔兰的地图可以看作是无限的坐标平面。每个整数坐标点上都有一座建筑,且每座建筑都通过街道与四个相邻建筑相连。所有街道均平行于坐标轴。
首都的主校位于 (sx,sy)。有 n 名学生就读于这所学校,其中第 i 名学生住在坐标为 (xi,yi) 的房屋中。可能有若干学生住在同一栋房屋中,但没有任何学生住在 (sx,sy) 处。
放学后,每名学生都从学校出发,沿一条最短路径步行回家。因此,第 i 名学生从学校到其家的距离为 ∣sx−xi∣+∣sy−yi∣。
贝尔兰供应部决定在首都某处(即某个整数坐标点)开设一个沙威玛摊位。若从学校到第 i 名学生家的至少一条最短路径经过沙威玛摊位所在位置,则认为第 i 名学生会购买沙威玛。禁止将沙威玛摊位设在学校所在位置 (sx,sy),但沙威玛摊位的坐标可以与某名(甚至多名)学生的住所坐标重合。
你希望找出最多可能有多少名学生会购买沙威玛,以及实现该最大值的沙威玛摊位最优位置。
输入格式
The first line contains three integers n, sx, sy (1≤n≤200000, 0≤sx,sy≤109) — the number of students and the coordinates of the school, respectively.
Then n lines follow. The i-th of them contains two integers xi, yi (0≤xi,yi≤109) — 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.
第一行包含三个整数 n、sx、sy(1≤n≤200000,0≤sx,sy≤109),分别表示学生人数以及学校的坐标。
接下来是 n 行。其中第 i 行包含两个整数 xi、yi(0≤xi,yi≤109),表示第 i 名学生所居住的房屋位置。某些房屋位置可能重合,但没有任何学生住在与学校相同的位置。
输出格式
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 px and py — the coordinates where the tent should be located. If there are multiple answers, print any of them. Note that each of px and py should be not less than 0 and not greater than 109.
输出应包含两行。第一行应包含一个整数 c —— 在帐篷处购买沙威玛的学生的最大人数。
第二行应包含两个整数 px 和 py —— 帐篷应放置的坐标。若存在多个答案,输出任意一个即可。注意,px 和 py 均应不小于 0 且不大于 109。
输入输出样例
输入#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.
在第一个例子中,如果我们把沙瓦玛摊位建在 (4,2),那么住在 (4,2)、(4,1) 和 (5,1) 的学生都会来光顾。
在第二个例子中,可以将沙瓦玛摊位建在 (1,1),这样住在 (0,0) 的两名学生都会来光顾。
输入解题思路,AI测评打分。不知道怎么写?