办事处选址
编程实现:
现将某区域的地图变成一个平面的方格图,平面上有n处居民住宅,已知n处居民住宅,每处居民住宅位置所处的行数和列数,现计划设置一处便民办事处,使办事处去到各个住宅位置的距离之和最短(只能上下左右走,且办事处可以和住宅处在同一个方格),请问最短距离之和是多少?
例如:共有两处居民住宅,位置如下图:
第一处居民住宅在0行0列,第二处居民住宅在0行1列,那么办事处可设置在0行0列处,到第一处居民住宅的距离为0,到第二处居民住宅的距离为1,最短距离之和为1。
输入描述
第一行输入一个正整数n,表示有n处居民住宅(1≤n≤10000)。
第二行往后n行,每一行输入一对数字,表示每处居民住宅的行数和列数(0≤行数<100,0≤列数<100),中间用空格隔开。
输出描述
输出最短距离之和。
输入样例
2 0 0 0 1
输出样例
1