2381번: 최대 거리

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


$O(n)$

(a,b), (c,d)인 점의 맨하탄 거리는 max(abs((a+b)-(c+d)),abs((a-b)-(c-d)))이다.

#include<cstdio>
#include<algorithm>
using namespace std;
int l1 = 1e9, h1 = -1e9, l2 = 1e9, h2 = -1e9, n;
int main() {
    scanf("%d", &n);
    for (int i = 0, x, y; i < n; i++) {
        scanf("%d %d", &x, &y);
        l1 = min(l1, x + y);
        h1 = max(h1, x + y);
        l2 = min(l2, x - y);
        h2 = max(h2, x - y);
    }
    printf("%d", max(h1 - l1, h2 - l2));
    return 0;
}