There is an infinite integer grid where  N people live in N different houses. They decide to create a meeting point at one person's house.   

From any given cell, all 8 adjacent cells can be reached in 1 unit of time, e.g. (x,y) can be reached from (x-1,y+1) in one unit of time. Find a common meeting place which minimizes the combined travel time of everyone.  

Input Format 

A positive integer N that denotes N houses or people.

The following N lines will contain two integers x,y each that denote the coordinates of the respective house.  

Output Format 

An integer, M, that denotes the minimum combined travel time of everyone.  

Constraints 

N <= 10^{5} 

The absolute value of each co-ordinate in the input will be at most 10^{9}

HINT: You may need 64-bit integer.

Input #1  

4 
0 1
2 5 
3 1 
4 0 

Output #1 

8
 
Explanation 

The houses will have a travel-sum of 11, 13, 8, or 10. 8 is the minimum.

Input #2   

6 
12 -14 
-3 3 
-14 7 
-14 -3 
2 -12 
-1 -6

Output #2:

54

Difficulty: MEDIUM_HARD
Tags: Geometry

Starter code:

Solutions:
x = []
y = []
n = int(input())
rt = 0
for i in range(n):
	(xi, yi) = [int(i) for i in input().strip().split()]
	x.append(xi)
	y.append(yi)

def dist(x, y):
	return (x ** 2 + y ** 2) ** 0.5
(xm, ym) = (sum(x) / n, sum(y) / n)

def find():
	ch = dist(x[0] - xm, y[0] - ym)
	k = 0
	for i in range(1, n):
		d = dist(x[i] - xm, y[i] - ym)
		if ch > d:
			ch = d
			k = i
	return k
rn = find()
rt = sum(map(lambda k, l: max(k, l), map(lambda k: abs(k - x[rn]), x), map(lambda k: abs(k - y[rn]), y)))
print(rt)


import sys
from math import sqrt
sum_x = 0.0
sum_y = 0.0

def find_closest(avg_x, avg_y):
	min_distance = sqrt((x[0] - avg_x) ** 2 + (y[0] - avg_y) ** 2)
	for i in range(no_of_houses):
		if sqrt((x[i] - avg_x) ** 2 + (y[i] - avg_y) ** 2) < min_distance:
			closest_x = x[i]
			closest_y = y[i]
			min_distance = sqrt((x[i] - avg_x) ** 2 + (y[i] - avg_y) ** 2)
	return (closest_x, closest_y)

def find_travel(closest_x, closest_y):
	travel = 0
	for i in range(no_of_houses):
		travel = travel + max(abs(x[i] - closest_x), abs(y[i] - closest_y))
	return travel
no_of_houses = int(sys.stdin.readline())
x = [0 for i in range(no_of_houses)]
y = [0 for i in range(no_of_houses)]
for i in range(no_of_houses):
	co_ordinates = sys.stdin.readline()
	co_ordinates = co_ordinates.split(' ')
	x[i] = int(co_ordinates[0])
	temp_y = co_ordinates[1].split('\n')
	y[i] = int(temp_y[0])
	sum_x = sum_x + x[i]
	sum_y = sum_y + y[i]
avg_x = sum_x / no_of_houses
avg_y = sum_y / no_of_houses
(closest_x, closest_y) = find_closest(avg_x, avg_y)
travel = find_travel(closest_x, closest_y)
print(travel)


N = int(input())
points = []
mp = [0, 0]
for i in range(N):
	points.append([int(j) for j in input().split()])
	mp[0] += points[i][0]
	mp[1] += points[i][1]
mp[0] /= N
mp[1] /= N
minDist = 10 ** 17
minDist2 = 10 ** 17
for i in range(N):
	xDiff = abs(points[i][0] - mp[0])
	yDiff = abs(points[i][1] - mp[1])
	dist = xDiff + yDiff
	dist2 = max(xDiff, yDiff)
	if dist < minDist:
		minDist = dist
	if dist2 < minDist2:
		minDist2 = dist2
minPos = []
for i in range(N):
	xDiff = abs(points[i][0] - mp[0])
	yDiff = abs(points[i][1] - mp[1])
	dist = xDiff + yDiff
	dist2 = max(xDiff, yDiff)
	if dist == minDist:
		minPos.append(i)
	elif dist2 == minDist2:
		minPos.append(i)
sums = [0 for i in minPos]
for i in range(len(minPos)):
	for j in range(N):
		if minPos[i] == j:
			continue
		xDiff = abs(points[minPos[i]][0] - points[j][0])
		yDiff = abs(points[minPos[i]][1] - points[j][1])
		sums[i] += max(xDiff, yDiff)
sums.sort()
print(sums[0])


import math

def abso(a):
	if a < 0:
		return -a
	else:
		return a
(absx, absy) = (0, 0)
n = int(input())
mat = []
for i in range(n):
	a = [int(i) for i in input().split(' ')]
	absx += a[0]
	absy += a[1]
	mat.append(a)
absx /= n
absy /= n
mi = math.sqrt((absx - mat[0][0]) ** 2 + (absy - mat[0][1]) ** 2)
point = 0
for i in range(1, n):
	di = math.sqrt((absx - mat[i][0]) ** 2 + (absy - mat[i][1]) ** 2)
	if di < mi:
		mi = di
		point = i
res = 0
for i in range(n):
	res += max(abso(mat[point][0] - mat[i][0]), abso(mat[point][1] - mat[i][1]))
print(res)


N = int(input())
(sx, sy, M) = (0, 0, [])
for n in range(0, N):
	m = [int(x) for x in input().strip().split(' ')]
	M.append(m)
	sx += m[0]
	sy += m[1]
(s, b) = ((sx / N, sy / N), M[0])
d = abs(b[0] - s[0]) + abs(b[1] - s[1])
for m in M:
	dm = abs(m[0] - s[0]) + abs(m[1] - s[1])
	if dm < d:
		d = dm
		b = m
sd = 0
for m in M:
	sd += max(abs(m[0] - b[0]), abs(m[1] - b[1]))
sd1 = sd
(s, b) = ((sx / N, sy / N), M[0])
d = abs(b[0] - s[0]) + abs(b[1] - s[1])
for m in M:
	dm = max(abs(m[0] - s[0]), abs(m[1] - s[1]))
	if dm < d:
		d = dm
		b = m
sd = 0
for m in M:
	sd += max(abs(m[0] - b[0]), abs(m[1] - b[1]))
print(min(sd, sd1))


def meetingPoint(x, y):
	ax = 0
	ay = 0
	nx = len(x)
	for i in range(nx):
		ax += x[i]
		ay += y[i]
	ax /= nx
	ay /= nx
	pos = 0
	mini = (x[0] - ax) * (x[0] - ax) + (y[0] - ay) * (y[0] - ay)
	for i in range(1, nx):
		temp = (x[i] - ax) * (x[i] - ax) + (y[i] - ay) * (y[i] - ay)
		if temp < mini:
			mini = temp
			pos = i
	ans = 0
	for i in range(nx):
		ans += max(abs(x[i] - x[pos]), abs(y[i] - y[pos]))
	return ans
a = int(input())
x = [0] * a
y = [0] * a
for i in range(0, a):
	b = input().strip()
	b = list(map(int, b.split(' ')))
	x[i] = b[0]
	y[i] = b[1]
print(meetingPoint(x, y))


import sys
from heapq import nsmallest

class Point:

	def __init__(self, x=0, y=0):
		self.x = x
		self.y = y

def distance(pointA, pointB):
	return max(abs(pointA.x - pointB.x), abs(pointA.y - pointB.y))

def medianApproximation(previousMedian, points):
	W = x = y = 0
	for point in points:
		d = distance(previousMedian, point)
		if d != 0:
			w = 1.0 / d
			W += w
			x += point.x * w
			y += point.y * w
	return Point(x / W, y / W)

def totalDistance(meetingPoint, points):
	return sum((distance(meetingPoint, point) for point in points))

def meetingPointDistance(dataStream, epsilon=100, k=100):
	numPoints = int(dataStream.readline())
	points = []
	median = Point()
	for i in range(0, numPoints):
		(x, y) = [int(z) for z in dataStream.readline().split()]
		points.append(Point(x, y))
		median.x = median.x + x
		median.y = median.y + y
	median.x = median.x // numPoints
	median.y = median.y // numPoints
	while True:
		newMedian = medianApproximation(median, points)
		dist = distance(median, newMedian)
		median = newMedian
		if dist < epsilon:
			break
	closestPoints = nsmallest(k, points, key=lambda p: distance(median, p))
	closestPoint = min(closestPoints, key=lambda p: totalDistance(p, points))
	return totalDistance(closestPoint, points)

def fromFile(dataFile):
	with open(dataFile) as f:
		return meetingPointDistance(f)
print(meetingPointDistance(sys.stdin))


from sys import stderr
from collections import Counter

def meetingPoint(pts):
	if len(pts) < 2:
		return 0
	costsum = getcosttable((x + y for (x, y) in pts))
	costdiff = getcosttable((x - y for (x, y) in pts))
	(mincost, x0, y0) = min(((costsum[x + y] + costdiff[x - y], x, y) for (x, y) in pts))
	return sum((kingsdist((x0, y0), pt) for pt in pts))

def getcosttable(diag):
	count = Counter(diag)
	total = sum(count.values())
	npast = 0
	diaglist = iter(sorted(count.keys()))
	lastdiag = next(diaglist, None)
	ans = {lastdiag: 0}
	for curdiag in diaglist:
		npast += count[lastdiag]
		ans[curdiag] = ans[lastdiag] + (2 * npast - total) * (curdiag - lastdiag)
		lastdiag = curdiag
	return ans

def kingsdist(pt1, pt2):
	return max((abs(x1 - x2) for (x1, x2) in zip(pt1, pt2)))

def main():
	a = int(input())
	pts = []
	for i in range(0, a):
		b = input().strip()
		b = list(map(int, b.split(' ')))
		pts.append(b)
	print(meetingPoint(pts))
main()


import sys
source = sys.stdin

def commute(H, m):
	total = 0
	(xm, ym) = m
	for (x, y) in H:
		total += max(abs(x - xm), abs(y - ym))
	return total
H = []
N = int(source.readline())
for _ in range(N):
	(x, y) = tuple([int(s) for s in source.readline().split()])
	H.append((x, y))
H_prime = [(x + y, x - y) for (x, y) in H]
A = sorted([a for (a, b) in H_prime])
B = sorted([b for (a, b) in H_prime])
start_a = A[0] - 1
if start_a % 2 != 0:
	start_a -= 1
start_b = B[0] - 1
if start_b % 2 != 0:
	start_b -= 1
F_a = {}
G_a = {}
F_a[start_a] = 0
G_a[start_a] = 0
last_element = start_a
for a in A:
	if a != last_element:
		F_a[a] = F_a[last_element] + 1
		G_a[a] = G_a[last_element] + F_a[last_element] * (a - last_element)
	else:
		F_a[a] += 1
	last_element = a
F_b = {}
G_b = {}
F_b[start_b] = 0
G_b[start_b] = 0
last_element = start_b
for b in B:
	if b != last_element:
		F_b[b] = F_b[last_element] + 1
		G_b[b] = G_b[last_element] + F_b[last_element] * (b - last_element)
	else:
		F_b[b] += 1
	last_element = b
min_change_black = 0
best_house_black = -1
for i in range(len(H_prime)):
	(a, b) = H_prime[i]
	if a % 2 == 0:
		change = G_a[a] + G_b[b]
		change -= ((a - start_a) // 2 + (b - start_b) // 2) * N
		if change < min_change_black:
			min_change_black = change
			best_house_black = i
start_x = (start_a + start_b) // 2
start_y = (start_a - start_b) // 2
start_commute = commute(H, (start_x, start_y))
best_commute_black = start_commute + min_change_black
start_a += 1
start_b += 1
min_change_white = 0
best_house_white = -1
for i in range(len(H_prime)):
	(a, b) = H_prime[i]
	if a % 2 != 0:
		change = G_a[a] + G_b[b]
		change -= ((a - start_a) // 2 + (b - start_b) // 2) * N
		if change < min_change_white:
			min_change_white = change
			best_house_white = i
start_x = (start_a + start_b) // 2
start_y = (start_a - start_b) // 2
start_commute = commute(H, (start_x, start_y))
best_commute_white = start_commute + min_change_white
ans = min(best_commute_black, best_commute_white)
print(ans)


def meetingPoint(x, y):
	cx = round(sum(x) / len(x))
	cy = round(sum(y) / len(y))
	distances = [(abs(cx - _x), abs(cy - _y)) for (_x, _y) in zip(x, y)]
	min_distances = [min(distances, key=lambda pair: max(pair)), min(distances, key=lambda pair: sum(pair))]
	indexes = [distances.index(md) for md in min_distances]
	total_distances = [sum([max(abs(x[i] - _x), abs(y[i] - _y)) for (_x, _y) in zip(x, y)]) for i in indexes]
	return min(total_distances)
a = int(input())
x = [0] * a
y = [0] * a
for i in range(0, a):
	b = input().strip()
	b = list(map(int, b.split(' ')))
	x[i] = b[0]
	y[i] = b[1]
print(meetingPoint(x, y))


def dist(a, b):
	return max(abs(a[0] - b[0]), abs(a[1] - b[1]))

def distCar(a, b):
	x = abs(a[0] - b[0])
	y = abs(a[1] - b[1])
	return x * x + y * y

def cent(lis):
	sx = 0
	sy = 0
	for (x, y) in lis:
		sx += x
		sy += y
	return (sx / len(lis), sy / len(lis))
n = int(input())
lis = []
for _ in range(n):
	(x, y) = list(map(int, input().split()))
	lis.append((x, y))
c = cent(lis)
d = 2 ** 63
temp = 0
for a in lis:
	if distCar(a, c) < d:
		temp = a
		d = distCar(a, c)
res = 0
for b in lis:
	res += dist(temp, b)
print(res)


def sumDistances(pt, res):
	n = len(pt)
	dist = sum((x[0] - pt[0][0] for x in pt))
	res[pt[0][1]] = res[pt[0][1]] + dist
	prev = dist
	for i in range(1, n):
		idx = pt[i][1]
		dx = pt[i][0] - pt[i - 1][0]
		dist = prev + i * dx - (n - i) * dx
		res[idx] = res[idx] + dist
		prev = dist
	return res

def meetingPoint(x, y):
	u = []
	v = []
	for i in range(len(x)):
		u.append(((x[i] + y[i]) / 2, i))
		v.append(((x[i] - y[i]) / 2, i))
	u.sort()
	v.sort()
	manhattan_dist = [0] * len(u)
	sumDistances(u, manhattan_dist)
	sumDistances(v, manhattan_dist)
	answer = int(min(manhattan_dist))
	return answer
a = int(input())
x = [0] * a
y = [0] * a
for i in range(0, a):
	b = input().strip()
	b = list(map(int, b.split(' ')))
	x[i] = b[0]
	y[i] = b[1]
print(meetingPoint(x, y))


N = int(input())
P = [tuple(map(int, input().split())) for _ in range(N)]
A = sorted(((x + y, i) for (i, (x, y)) in enumerate(P)))
B = sorted(((x - y, i) for (i, (x, y)) in enumerate(P)))
SA = sum((A[i][0] - A[0][0] for i in range(1, N)))
SB = sum((B[i][0] - B[0][0] for i in range(1, N)))
M = [0] * N
M[A[0][1]] += SA
M[B[0][1]] += SB
for i in range(1, N):
	SA += (A[i][0] - A[i - 1][0]) * (i - (N - i))
	SB += (B[i][0] - B[i - 1][0]) * (i - (N - i))
	M[A[i][1]] += SA
	M[B[i][1]] += SB
print(min(M) // 2)


def dist(p0, p1):
	return max(abs(p0[0] - p1[0]), abs(p0[1] - p1[1]))

def travel_from(coordinates, p0):
	return sum((dist(p0, p) for p in coordinates))

def solve_slow(coordinates):
	x0 = sum((p[0] / len(coordinates) for p in coordinates))
	y0 = sum((p[1] / len(coordinates) for p in coordinates))
	c = sorted(coordinates, key=lambda p: dist(p, (x0, y0)))
	return min((travel_from(coordinates, p0) for p0 in c[0:250]))

def comp_dist(values):
	comp = ((i, c) for (i, c) in enumerate(values))
	sorted_by = sorted(comp, key=lambda x: x[1])
	N = len(sorted_by)

	def sums():
		s = sum((v - sorted_by[0][1] for (_, v) in sorted_by))
		yield (sorted_by[0][0], s)
		for (i, (idx, v)) in enumerate(sorted_by[1:], 1):
			d = v - sorted_by[i - 1][1]
			s = s + d * i - d * (N - i)
			yield (idx, s)
	res = [0] * N
	for (i, v) in sums():
		res[i] = v
	return res

def solve(coordinates):
	x_dist = comp_dist((x + y for (x, y) in coordinates))
	y_dist = comp_dist((x - y for (x, y) in coordinates))
	return int(min((x + y for (x, y) in zip(x_dist, y_dist))) / 2)
n = int(input())
coordinates = []
for _ in range(n):
	coordinates.append(list(map(int, input().rstrip().split())))
result = solve(coordinates)
print(result)