주어진 점들 중 최대 맨해튼 거리(Manhattan Distance)를 빠르게 찾는 방법

https://atcoder.jp/contests/abc178/tasks/abc178_e

E - Dist Max

 

 

 

n개의 점이 주어질때, 이들 쌍으로 만들 수 있는 가장 긴 맨해튼 거리는?

 

n이 최대 20만이기 때문에 $O(N^2)$으로 직접 비교할 수는 없다

 

두 점 (xi,yi), (xj,yj)에 대하여 맨해튼 거리는 |xi - xj| + |yi - yj| = A

 

A는 xi,xj, yi,yj 사이 대소관계에 따라 다음과 같이 풀어낼 수 있다

 

1) $x_{i} >= x_{j}$이고 $y_{i} >= y_{j}$이면

 

$x_{i} - x_{j} + y_{i} - y_{j} = x_{i} + y_{i} - (x_{j} + y_{j})$

 

2) $x_{i} >= x_{j}$ 이고 $y_{i} < y_{j}$ 이면

 

$x_{i} - x_{j} - (y_{i} - y_{j}) = x_{i} - y_{i} - (x_{j} - y_{j})$

 

3) $x_{i} < x_{j}$ 이고 $y_{i} >= y_{j}$ 이면

 

$- (x_{i} - x_{j}) + (y_{i} - y_{j}) = - (x_{i} - y_{i}) + (x_{j} - y_{j})$

 

4) $x_{i} < x_{j}$  이고 $y_{i} < y_{j}$ 이면

 

$- (x_{i} - x_{j}) - (y_{i} - y_{j}) = - (x_{i} + y_{i}) + (x_{j} + y_{j})$

 

항상 양수가 되도록 절댓값을 제거한 것이므로 4가지 모두 양수이다.

 

여기서 핵심은 필요한 것은 (xi+yi), (xi-yi), (xj+yj), (xj-yj) 4가지이다.

 

따라서 (xi+yi)와 (xi-yi)를 각각 O(N)에 구한 다음

 

1) (xi+yi)의 최댓값 - (xi+yi)의 최솟값

 

2) (xi-yi)의 최댓값 - (xi-yi)의 최솟값

 

중 더 큰 값을 구하면 될 것이다.

 

n = int(input())

A = []
B = []

for _ in range(n):
    
    x,y = map(int,input().split())
    A.append(x+y)
    B.append(x-y)

A.sort()
B.sort()

print(max((A[-1] - A[0]), (B[-1] - B[0])))

 

 

참고로 모든 실수 a,b에 대해 $|a| + |b| = max(|a+b|, |a-b|)$이다.

 

왜냐하면 |a| = max(a,-a)이므로

 

$|a| + |b| = max(a,-a) + max(b,-b) = max(a+b,-(a+b), -(a-b), a-b) = max(|a+b|, |a-b|)$

 

 

<똑같은 문제>

 

 

2381번: 최대 거리