테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.

====== 최대 거리 ======

===== 풀이 =====
  * [[ps:tutorial:가장_멀리_떨어진_두_점#맨해튼_거리를_기준으로_할_경우|맨해튼 거리로 가장 멀리 떨어진 두 점]]을 찾는 문제.
  * 풀이 방법은 링크에 설명되어있다. 시간복잡도는 O(n)

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 2381. 최대 거리".

- Problem link: https://www.acmicpc.net/problem/2381
- Solution link: http://www.teferi.net/ps/problems/boj/2381

Tags: [geometry]
"""

import sys


def farthest_points_pair_manhattan(points):
    sums = [x + y for x, y in points]
    max_sum, min_sum = max(sums), min(sums)
    diffs = [x - y for x, y in points]
    max_diff, min_diff = max(diffs), min(diffs)
    return max(max_sum - min_sum, max_diff - min_diff)


def main():
    N = int(sys.stdin.readline())
    points = [[int(x) for x in sys.stdin.readline().split()] for _ in range(N)]

    print(farthest_points_pair_manhattan(points))


if __name__ == '__main__':
    main()
</dkpr>

{{tag>BOJ ps:problems:boj:골드_3}}