2381 최대거리

문제

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

풀이

• 두 점 사이의 최대 맨하탄 거리를 구하는 문제이다.
• 맨하탄 거리는 유클리드 거리에 비해 식이 간단하다(?)
• 따라서 절대값에 따라 식을 정리할 수 있다.
• 두 점 (x1,y1),(x2,y2)의 맨하탄 거리는 |x1-x2| + |y1-y2|이다.
  1. x1 - x2 + y1 - y2 = (x1+y1) - (x2+y2)
  2. x1 - x2 - y1 + y2 = (x1-y1) - (x2-y2)
  3. -x1 + x2 + y1 - y2 = -(x1-y1) + (x2-y2)
  4. -x1 + x2 - y1 + y2 = -(x1+y1) + (x2+y2)
• 위 네개의 케이스의 최댓값을 구하기 위해 x,y의 합과 차가 필요하고, 그것을 기준으로 정렬하면 된다.
• 결론적으로, x+y에 대해 정렬해서 첫번째와 마지막 점에 대해 값을 계산하고, x-y에 대해 정렬해서 첫번째와 마지막 점에 대해 값을 계산한다.