백준 2381 <최대 거리> Python

https://www.acmicpc.net/problem/2381

---

|a-c| + |b-d| 은 각 절댓값 기호 안의 부호에 따라  
(a+b) - (c+d) (a>=c and b>=d)
(c+d) - (a+b) (a<c and b<d)
(a-b) - (c-d) (a>=c and b<d)
(c-d) - (a-b) (a<c and b>=d)

로 나눌 수 있습니다.

 

또 이들을 관찰하면 모든 수식이 (a+b) (c+d) (a-b) (c-d) 로 이루어져 있음을 알 수 있습니다.

그렇다면 모든 좌표에 대해 x+y 와 x-y 를 계산해놓고 정렬한 뒤 두 계산값들에 대한 각각의 (최댓값과 최솟값의 차) 중 큰 값을 출력하면 해답을 도출할 수 있습니다.

 

---

import sys

input = sys.stdin.readline


def solution(N, idxs):
    sums = list(sorted([x+y for x, y in idxs]))
    subs = list(sorted([x-y for x, y in idxs]))

    print(max(sums[-1]-sums[0], subs[-1]-subs[0]))


# 입력
N = int(input().strip())
idxs = [list(map(int, input().strip().split())) for _ in range(N)]

solution(N, idxs)