[백준]#2381 최대 거리

문제

N(1 ≤ N ≤ 50,000)개의 점들이 있을 때, 최대 L1-metric 거리를 찾으시오.

두 점의 좌표가 (a, b), (c, d)일 때, 두 점의 L1-metric 거리는 |a-c|+|b-d|이다.

입력

첫째 줄에 N이 주어진다. 다음 N개의 줄에는 각 점의 x, y좌표가 주어진다. 각 좌표의 범위는 -1,000,000이상 1,000,000이하이다.

출력

첫째 줄에 최대 거리를 출력한다.

예제 입력 1

5
1 1
3 5
2 7
8 1
4 4

예제 출력 1

12

풀이

이 문제는 이중for문으로 풀면 시간초과가 나기 때문에 시간복잡도를 O(n)으로 풀 수 있는 방법을 찾아야한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        Pair[] arr = new Pair[N];

        for(int i=0; i<N; i++) {
            String[] input = br.readLine().split(" ");
            arr[i] = new Pair(Integer.parseInt(input[0]), Integer.parseInt(input[1]));
        }
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;

        for(int i=0; i<N; i++) {
            max = Math.max(max, arr[i].x+arr[i].y);
            min = Math.min(min, arr[i].x+arr[i].y);
        }
        int result1 = max-min;

        max = Integer.MIN_VALUE;
        min = Integer.MAX_VALUE;

        for(int i=0; i<N; i++) {
            max = Math.max(max, arr[i].x-arr[i].y);
            min = Math.min(min, arr[i].x-arr[i].y);
        }
        int result2 = max-min;

        System.out.println(Math.max(result1, result2));
    }

    static class Pair {
        int x;
        int y;

        public Pair(int x, int y) {
            this.x=x;
            this.y=y;
        }
    }
}