La formiga prudent P79091

Statement

thehtml

Considereu un mon pla infinit enrajolat com es pot veure a la figura. Una formiga es troba a la posició (x₁, y₁) i vol anar a (x₂, y₂), amb totes quatre coordenades enteres. Com que la formiga és prudent, no vol travessar cap rajola, i només vol moure’s per les juntures per passar desapercebuda. Quina distància mínima haurà de desplaçar-se?

Per exemple, la figura mostra un possible camí òptim entre (−4, 2) i (−1, 1), i també un entre (4, −1) i (3, 2).

(12,8) unit=0.7cm, linewidth=0.7

linecolor=blue

-(0.5,2)(11.5,2) -(0.5,3)(11.5,3) -(0.5,4)(11.5,4) -(0.5,5)(11.5,5) -(0.5,6)(11.5,6) -(0.5,7)(11.5,7) -(1,1.5)(1,2) -(1,3)(1,4) -(1,5)(1,6) -(1,7)(1,7.5) -(3,1.5)(3,2) -(3,3)(3,4) -(3,5)(3,6) -(3,7)(3,7.5) -(5,1.5)(5,2) -(5,3)(5,4) -(5,5)(5,6) -(5,7)(5,7.5) -(7,1.5)(7,2) -(7,3)(7,4) -(7,5)(7,6) -(7,7)(7,7.5) -(9,1.5)(9,2) -(9,3)(9,4) -(9,5)(9,6) -(9,7)(9,7.5) -(11,1.5)(11,2) -(11,3)(11,4) -(11,5)(11,6) -(11,7)(11,7.5) -(2,2)(2,3) -(2,4)(2,5) -(2,6)(2,7) -(4,2)(4,3) -(4,4)(4,5) -(4,6)(4,7) -(6,2)(6,3) -(6,4)(6,5) -(6,6)(6,7) -(8,2)(8,3) -(8,4)(8,5) -(8,6)(8,7) -(10,2)(10,3) -(10,4)(10,5) -(10,6)(10,7)

(6,3.65)(0, 0) (10,3.3)(4, −1) (9,6.3)(3, 2) (2,5.65)(−4, 2) (5,4.65)(−1, 1)

[fillstyle=solid,fillcolor=black](6,4)0.1

linewidth=2pt linecolor=red -(10,3)(11,3) -(11,3)(11,4) -(11,4)(10,4) -(10,4)(10,5) -(10,5)(9,5) -(9,5)(9,6)

[fillstyle=solid,fillcolor=red](10,3)0.1 [fillstyle=solid,fillcolor=red](9,6)0.1

-(2,6)(3,6) -(3,6)(3,5) -(3,5)(5,5)

[fillstyle=solid,fillcolor=green](2,6)0.1 [fillstyle=solid,fillcolor=green](5,5)0.1

Entrada

L’entrada consisteix en diversos casos, cadascun amb x₁, y₁, x₂ i y₂, tots entre −10⁸ i 10⁸.

Sortida

Per a cada cas, escriviu la mínima distància entre els punts.

Observació

Podeu obtenir 40 punts resolent casos amb coordenades entre −100 i 100.

Public test cases

Input

-4 2 -1 1
4 -1 3 2

Output

4
6

Information

Author: Salvador Roura
Language: Catalan
Official solutions: C++
User solutions: C++ Python