P3439 [POI 2006] MAG-Warehouse

The streets of the New Byte City form a rectangular grid - those running east-west are simply called streets, while those running north-south are called avenues. To avoid mistakes, we shall call them h-streets and v-streets, respectively. The v-streets are numbered from $1$ to $500\ 000\ 000$ eastwards. Similarly, the h-streets are numbered from $1$ to $500\ 000\ 000$ northwards. Every v-street crosses every h-street and, conversely, every h-street crosses every v-street. The distance between two consecutive v-streets, as well as between two consecutive h-streets, is exactly one kilometre.  There are $k$ shops in the city, each one of them is situated at a crossroads. Byteasar, the merchant, supplies every single one of the $k$ shops, and furthermore he returns to some of them several times a day with fresh supplies. Recently he has decided to have a warehouse built, from which the goods would be delivered. For obvious reasons, it should stand at a crossroads. The lorry loaded with goods can supply only one shop per course - it leaves the warehouse, delivers to the shop and returns to the warehouse. The lorry always picks the shortest path from the warehouse to the shop, and the shortest one back (possibly the same one). The distance between points $(x_i, y_i)$ and $(x_j, y_j)$ equals $\max \{ |x_i - x_j|, |y_i - y_j| \}$. TaskWrite a programme that: reads the locations of shops, as well as the numbers of their daily deliveries, from the standard inputdetermines such a warehouse's position that the summary distance of the lorry's daily route is minimal,writes the result to the standard output. 给定一个网格图，其上有一堆坏点(整点，同一位置多个)，求一个整点，使得该整点到所有的坏点的**切比雪夫距离**之和最小。 求这个整点位置。(横纵坐标最大)

无

无

感谢@oscar 提供SPJ