boj 2381 : 최대거리

boj 2381 : 최대거리

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

n^2만에 해결할 수 있는 방법은 간단히 떠올릴 수 있다. 하지만 n이 최대 50000이기 때문에 시간초과.

nlongn 이하의 해결법을 찾아야한다.

답은 (x+y의 최대값) - (x+y의 최소값), (x-y의 최대값) - (x-y의 최소값) 둘 중 큰값이 답이다.

응???

증명을 해보자.

1. (x+y의 최대값) - (x+y의 최소값)이 답일 경우

1.1 앞 괄호를 (x1,y1), 뒷 괄호를 (x2,y2)라 두면,

1.2 x1 > x2이고, y1 > y2의 경우만 가능하다.

1.3 그렇다면 만약 x1 < x2이거나 y1 < y2라면? 답에 모순이 생기지 않을까?

x1 < x2이거나 y1 < y2라도 상관없다는것을 증명해보자.

1.4 x1 < x2라면 (x1+y1) - (x2+y2) 보다 (x2 - y2) - (x1 - y1) 가 더 크다.

1.5 왜냐하면, x1 - x2 + y1 - y2 < x2 - x1 + y1 - y2 이기 때문.

그러므로 (x-y의 최대값) - (x-y의 최소값)의 경우가 더 크므로 고려가 된다.

마찬가지로, y1 <y2 인 경우도 해당된다.

1.6 그렇다면 x1 < x2 이고 y1 < y2라면?

위의 경우는 불가능하다. x1 < x2 이고 y1 < y2라면 (x2+y2)가 (x1+y1)보다 크기 때문.

2. (x-y의 최대값) - (x-y의 최소값)이 답인 경우

2.1 1번의 유도과정과 마찬가지로 유도할 수 있다.

시간복잡도는 n으로 간단하게 문제를 해결할 수 있다.