Perfect gift

시간 제한2초메모리 제한1024 MB

요약
격자 위의 두 점이 이미 수놓아져 있을 때, 모서리 길이가 3칸 이상인 평행육면체의 테두리 위에 두 점이 놓이도록 채워야 하는 최소 십자수를 구한다.
난이도

어려움10점 중 8점

유형
기하, 수학, 완전 탐색, 구현
정답자
아직 제출이 없습니다

문제

Taja prepares a present for the birthday. As you might know, the best present is the one handcrafted by yourself. Recently she learnt cross-stitching and decided to make use of this skill.

At home she only managed to find a canvas, which already had two crosses stitched on it. Don't panic --- you can always complement it to the full picture. She had little experience, that's why she chose simple but nevertheless beautiful picture, which is parallelepiped. She wants to finish the present as soon as possible, thus number of new cross-stitches should be the least possible.

Parallelepiped on the infinite grid is drawn like this.

Let's draw a rectangle ABCDABCD with its upper left corner at AA and lower right corner at CC.

Then draw segments of equal length towards up-right from AA, BB and CC --- with ends at EE, FF, GG correspondingly. Then add segments EFEF and FGFG.

All edges of the parallelepiped should be at least 33 cells long.

입력

First line of the input contains two integers x_1x\_1 and y_1y\_1 --- coordinates of the first cross-stitch. Second line contains coordinates of second cross: x_2x\_2, y_2y\_2. Coordinates of the first cross-stitches are different. Axis OXOX is directed from left to right, and axis OYOY --- from the bottom to the top. All numbers are within range \[0,109]\[0, 10^9].

출력

Output should contain single number --- the least amount of required cross-stitches.

힌트

This pictures correspond to the samples:

예제2

  1. 예제 1

    입력
    4 2
    9 3
    
    예상 출력
    17
    
  2. 예제 2

    입력
    0 0
    1 1
    
    예상 출력
    14