문제
농부 창호가 농장을 짓고자 한다. 그에게 일하는 소 N(2≤N≤10,000)마리가 있는데, 소 i는 (Xi,Yi) (-10,000≤Xi,Yi≤10,000)에서 일한다.
각 소들에 대해서 상하좌우로 인접한 소는 없다.
창호는 이러한 소들을 위해 소들의 일하는 좌표랑 겹치지 않게 농장을 지어야한다. 그리고 각 소들이 농장으로 오는 맨하튼 거리의 합을 최소화 시키면서 농장을 짓고 싶어한다.
(X1,Y1)과 (X2,Y2)사이의 맨하튼 거리는 다음과 같이 정의된다. |X1-X2|+|Y1-Y2| 농장은 소들의 일하는 위치와 겹치지 않으면서 각 소들이 농장으로 오는 맨하튼 거리의 합의 최소값과, 최소값이 가능한 좌표의 개수를 구하자.
입력
입력의 첫 줄에는 N이 주어진다.
입력의 2번째 줄 부터 N+1까지 i+1번 줄에 Xi Yi 가 주어진다.
출력
소들이 농장으로 오는 맨하튼 거리의 합의 최소값과 가능한 농장의 좌표 개수를 출력한다.
예제
4
1 -3
0 1
-2 1
1 -1
10 4
로그인해야 코드를 작성할 수 있어요.