Asfia's daughter just turned 5. She is looking for a school to get her admitted. Like every other parent, she wants to admit her daughter to a popular school. But considering the countless number of schools present currently, finding the perfect school has become a cumbersome process. In this problem, we would like to help Asfia find a school for his daughter.
Consider that, Asfia lives in a 2D plane where infinitely many schools are situated. For all integers i and j, there is a school at coordinates (10i, 10j). Additionally, there are n houses at (x1, y1), (x2, y2), . . . (xn, yn). Each school at (10i, 10j) has a student from all houses (xi, yi) within Manhattan Distance of 10. That means, if |10i - xi| + |10j - yi| ≤ 10, one child from the house located at (xi, yi) studies in the school located at (10i, 10j). Assume that, each house has infinitely many children and multiple buildings can be situated in the same coordinate.
Asfia considers a school to be popular if it has students from lots of different houses. Now, she will provide you the coordinates of the n houses. Your job is to find the schools that have students from most number of different houses.
The first line of the input will contain a single integer N (1 ≤ N ≤ 105), denoting the number of houses.
The following N lines each will contain a pair of integers xi yi (0 ≤ xi, yi ≤ 109; 1 ≤ i ≤ N), separated by a space, denoting the coordinate of the ith house.
Output the coordinates of the most popular schools in the form x y. If there are multiple such schools, list them in ascending order of their x coordinates. If their x coordinate is same, then list them in ascending order of their y coordinates. Each coordinate must be separated by a newline.
2 2 7 4 13
The image shown above corresponds to the sample test case. A portion of the 2D grid is shown. The circles represent the schools and the two dots represent houses. The numbers beside the lines denote the Manhattan Distance between the corresponding houses and schools.
That means, the school located at (0, 10) has students from the most number of different houses.
Login to submit
We need to build an ordered hash table from school coordinates to the number of houses it has a stud...