시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 740 75 46 11.471%

문제

국민대학교에서 학생들의 방학을 즐겁게 보낼 수 있는 놀이동산 국민 랜드를 만들기로 하였다. 현우는 국민 랜드의 총 책임자로써, 놀이동산을 재미있게 만들기 위해 국민대학교 지도에서 임의의 네 점을 잡고, 이 네 점으로 이루어지는 사각형을 국민 랜드의 면적으로 사용하고자 결정하였다. 아래는 현우가 고른 네 점의 예시이다.

미적 요소를 중요하게 여긴 국민대학교에서는 현우의 제안을 거절하였다. 그리고 새로운 국민 랜드의 영역을 고르기 위한 조건을 추가하였다.

“국민 랜드는 한 변의 길이가 1 이상인 정사각형으로 만들어야한다. 정사각형 한 변의 길이는 정수만 가능하며 각 변은 x축 또는 y축과 평행해야 한다. 그리고 정사각형에서 대각선을 그었을 때, 두 대각선이 만나는 교점은 항상 (0,0) 이어야 한다.”

현우는 이제 기존에 찍었던 4개의 점을 이동시켜 조건을 만족하는 새로운 국민 랜드의 영역을 고르려고 한다. 처음 찍었던 점에서 작업이 진행될 것으로 예상하고 각 점에 인력을 배치한 현우는, 새로 지정되는 좌표로 사람들을 이동시켜야 한다. 이 때, 이동시키는 비용은 기존 좌표와 새로 지정되는 좌표를 연결하는 좌표의 맨해튼 거리(|xold-xnew|+|yold-ynew|)와 같다. 현우는 인력을 적절히 이동시켜 이동 비용이 최소화하는 지점을 국민 랜드의 영역으로 결정하기로 하였다. 아래 2개의 그림을 보자.

 

왼쪽 그림은 한 변의 길이가 8인 정사각형으로 계획을 변경한 모습이다. 이 때, 검은 점(기존 좌표)에서 빨잔 점(새로운 좌표)로 인력을 이동시키는데 필요한 비용의 최솟값은 7이 된다. 하지만 만약 오른쪽 그림처럼 한 변의 길이가 10인 정사각형으로 계획을 변경한다면, 인력을 이동시키는데 필요한 비용의 최솟값은 3이 되고, 어떠한 크기의 정사각형으로 계획을 변경하더라도 필요한 비용의 최솟값은 3보다 작아지지 않는다. 위와 같은 방법으로 현우의 계획을 수정하여, 인력의 이동비용이 최소가 되는 국민 랜드의 한 변의 길이를 구하는 프로그램을 작성하시오. 만약 최소 비용이 같은 정사각형이 여러 개 존재한다면, 그 중에서 더 큰 정사각형으로 국민 랜드를 만들기로 한다.

입력

입력 데이터는 표준 입력을 사용한다. 입력은 1개의 테스트 데이터로 구성된다. 입력은 4개의 줄로 이루어져 있으며, 각 줄에는 현우의 초기 계획에 해당하는 좌표 x,y가 각각 주어진다. 좌표의 범위는 |x,y|≤1,000,000,000 이다.

출력

출력은 표준 출력을 사용한다. 입력받은 데이터에 대해, 계획을 수정하였을 때 인력의 이동 비용이 최소가 되는 경우를 찾아, 그 정사각형의 한 변의 길이를 출력한다.

예제 입력

5 5
-5 5
-5 -5
3 -4

예제 출력

10

힌트