Cockroaches#2896
Every midnight in the apartment of the scientist Vasya, a horror begins. Hundreds... no, THOUSANDS of cockroaches emerge from every crevice to invade his dining table, devouring all crumbs and leftovers! Vasya despises cockroaches. After much thought, he invented a Super-trap that, once activated, attracts all cockroaches within a large area. He plans to activate the trap tonight. However, there is a problem: this highly effective trap, with its large working zone, consumes a huge amount of energy. Therefore, Vasya wishes to minimize the operating time of the trap.
Vasya has collected information about all the places where the cockroaches reside. He also noticed that cockroaches move only along the lines of his tablecloth at a constant speed (we can assume this speed is , so a cockroach in one section can move to any adjacent section, either vertically or horizontally, in unit of time). Vasya has decided to activate the trap in one of these sections. When the trap is activated, all the cockroaches will move toward the section containing the trap as quickly as possible. At any moment after activation, cockroaches always move toward the section with the trap, minimizing their distance to it. If there are two shortest paths, a cockroach may choose either one.
Write a program for Vasya that selects the section which minimizes the time required to eliminate all cockroaches. The tablecloth should be considered a plane with a Cartesian coordinate system, and the sections are points with integer coordinates.
The first line contains a single integer (1 \le n \le 10000), the number of places where cockroaches live. The following lines each contain the and coordinates of a place where cockroaches live (integers whose absolute values are not greater than some bound).
You must output two integers and —the coordinates of the section that minimizes the required time. If there is more than one solution, output any one of them.
Example 1