|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|1 초||512 MB||0||0||0||0.000%|
There are N police stations in Flatland and the ith police station is located at a coordinate (xi, yi). The authority plans to increase the synergy between these police stations by reducing any miscommunication that often arises among them. To do this, the authority decides to build a new tower that will serve as the Communication Control Center (CCC). Note that the CCC can only be built on (x, y) where both x and y are integers. It does not matter whether there is already a police station at (x, y), CCC can be built along with that police station.
CCC then will draw a communication cable to each of the police stations with some restrictions.
Due to some weird physics law in Flatland, each cable can only have a length of at most L in x-axis direction and a length of at most W in y-axis direction; this is the reason why this type of cable is known as hL, Wi cable in Flatland. To have stable communication, all police stations should be connected by the same type of cable.
Recent science and technology advancements in Flatland allows the physicists to build an hL, Wi cable for any L and W they like, with a cost. As the cost becomes quite expensive for larger L and W, the authority needs to figure out L and W that can satisfy their need, i.e. to connect all police stations with CCC, while minimizing the value of L + W.
Your task in this problem is to find L and W such that the value of L + W is minimum and the authority can build CCC at (x, y) where both x and y are integers while all police stations can be connected to the CCC with hL, Wi cables. If there are multiple solutions, minimize L first, and then minimize W.
Input begins with a line containing an integer: N (1 ≤ N ≤ 100 000) representing the number of police stations in Flatland. The next N lines each contains two integers: xi yi (−106 ≤ xi, yi ≤ 106) representing the location of each police station.
Output in a line two integers (separated by a single space), L and W, respectively, such that the value of L + W is minimum and the authority can build CCC at (x, y) where both x and y are integers while all police stations can be connected to the CCC with hL, Wi cables. If there are multiple solutions, minimize L first, and then minimize W.
5 20 90 -10 40 90 20 50 -30 50 70
The optimal decision that can be made by the authority is to build the CCC at (40, 30) and prepare for h50, 60i cables to connect all police stations to the CCC.
2 120 740 122 749
To have a minimum L+W, the CCC must be built at (121, 744) or (121, 745). Either way, they will need h1, 5i cables to connect both police stations to the CCC.
5 -30 -7 2 80 23 15 31 30 92 -20
The optimal decision that can be made by the authority is to build the CCC at (31, 30) and prepare for h61, 50i cables to connect all police stations to the CCC.