Four Points (Codeforces 1455E)
Tags: Greedy, ternary search

You are given four different integer points $$$p_1$$$, $$$p_2$$$, $$$p_3$$$ and $$$p_4$$$ on $$$\mathit{XY}$$$ grid.In one step you can choose one of the points $$$p_i$$$ and move it in one of four directions by one. In other words, if you have chosen point $$$p_i = (x, y)$$$ you can move it to $$$(x, y + 1)$$$, $$$(x, y - 1)$$$, $$$(x + 1, y)$$$ or $$$(x - 1, y)$$$.Your goal to move points in such a way that they will form a square with sides parallel to $$$\mathit{OX}$$$ and $$$\mathit{OY}$$$ axes (a square with side $$$0$$$ is allowed).What is the minimum number of steps you need to make such a square?

Input: The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.Each test case consists of four lines. Each line contains two integers $$$x$$$ and $$$y$$$ ($$$0 \le x, y \le 10^9$$$) — coordinates of one of the points $$$p_i = (x, y)$$$.All points are different in one test case.

Output: For each test case, print the single integer — the minimum number of steps to make a square.

Note: In the first test case, one of the optimal solutions is shown below:    Each point was moved two times, so the answer $$$2 + 2 + 2 + 2 = 8$$$.In the second test case, one of the optimal solutions is shown below:    The answer is $$$3 + 1 + 0 + 3 = 7$$$.In the third test case, one of the optimal solutions is shown below:    The answer is $$$1 + 1 + 2 + 1 = 5$$$.

Sample Inputs:
3
0 2
4 2
2 0
2 4
1 0
2 0
4 0
6 0
1 6
2 2
2 5
4 1

Sample Outputs:
8
7
5

Solution (Python):
import sys, os, io
input = sys.stdin.readline
T = int(input())
ans = [0] * T
for t in range(T):
    (X, Y) = ([0] * 4, [0] * 4)
    A = [0] * 4
    for i in range(4):
        (X[i], Y[i]) = map(int, input().split())
        A[i] = [X[i], Y[i]]
    X.sort()
    Y.sort()
    A.sort()
    cnt = 0
    for i in range(2):
        rank = 1
        for j in range(4):
            if A[i][1] < A[j][1]:
                rank += 1
        if rank <= 2:
            cnt += 1
    if cnt != 1:
        ans[t] += min(Y[2] - Y[1], X[2] - X[1]) * 2
    x_min = X[2] - X[1]
    x_max = X[3] - X[0]
    y_min = Y[2] - Y[1]
    y_max = Y[3] - Y[0]
    if not (x_max < y_min or y_max < x_min):
        ans[t] += X[3] - X[2] + (X[1] - X[0])
        ans[t] += Y[3] - Y[2] + (Y[1] - Y[0])
    elif x_max < y_min:
        ans[t] += X[3] - X[2] + (X[1] - X[0])
        ans[t] += Y[3] - Y[2] + (Y[1] - Y[0]) + 2 * (y_min - x_max)
    else:
        ans[t] += X[3] - X[2] + (X[1] - X[0]) + 2 * (x_min - y_max)
        ans[t] += Y[3] - Y[2] + (Y[1] - Y[0])
print(*ans, sep='\n')

Solution (Python):
T = int(input())
ans = [0] * T
for t in range(T):
    (X, Y) = ([0] * 4, [0] * 4)
    A = [0] * 4
    for i in range(4):
        (X[i], Y[i]) = map(int, input().split())
        A[i] = [X[i], Y[i]]
    X.sort()
    Y.sort()
    A.sort()
    cnt = 0
    for i in range(2):
        rank = 1
        for j in range(4):
            if A[i][1] < A[j][1]:
                rank += 1
        if rank <= 2:
            cnt += 1
    if cnt != 1:
        ans[t] += min(Y[2] - Y[1], X[2] - X[1]) * 2
    x_min = X[2] - X[1]
    x_max = X[3] - X[0]
    y_min = Y[2] - Y[1]
    y_max = Y[3] - Y[0]
    if x_max < y_min:
        ans[t] += X[3] - X[2] + (X[1] - X[0])
        ans[t] += Y[3] - Y[2] + (Y[1] - Y[0]) + 2 * (y_min - x_max)
    elif y_max < x_min:
        ans[t] += X[3] - X[2] + (X[1] - X[0]) + 2 * (x_min - y_max)
        ans[t] += Y[3] - Y[2] + (Y[1] - Y[0])
    else:
        ans[t] += X[3] - X[2] + (X[1] - X[0])
        ans[t] += Y[3] - Y[2] + (Y[1] - Y[0])
print(*ans, sep='\n')

Solution (Python):
import sys, os, io
input = sys.stdin.readline
from random import *
T = int(input())
ans = [0] * T
for t in range(T):
    (X, Y) = ([0] * 4, [0] * 4)
    A = [0] * 4
    for i in range(4):
        (X[i], Y[i]) = map(int, input().split())
        A[i] = [X[i], Y[i]]
    X.sort()
    Y.sort()
    A.sort()
    cnt = 0
    for i in range(2):
        rank = 1
        for j in range(4):
            if A[i][1] < A[j][1]:
                rank += 1
        if rank <= 2:
            cnt += 1
    if cnt != 1:
        ans[t] += min(Y[2] - Y[1], X[2] - X[1]) * 2
    x_min = X[2] - X[1]
    x_max = X[3] - X[0]
    y_min = Y[2] - Y[1]
    y_max = Y[3] - Y[0]
    if x_max < y_min:
        ans[t] += X[3] - X[2] + (X[1] - X[0])
        ans[t] += Y[3] - Y[2] + (Y[1] - Y[0]) + 2 * (y_min - x_max)
    elif y_max < x_min:
        ans[t] += X[3] - X[2] + (X[1] - X[0]) + 2 * (x_min - y_max)
        ans[t] += Y[3] - Y[2] + (Y[1] - Y[0])
    else:
        ans[t] += X[3] - X[2] + (X[1] - X[0])
        ans[t] += Y[3] - Y[2] + (Y[1] - Y[0])
print(*ans, sep='\n')