La formiga prudent P79091

Statement

0.5 Considereu un mon pla infinit enrajolat com es pot veure a la figura. Una formiga es troba a la posició $(x_1, y_1)$ i vol anar a $(x_2, y_2)$ , 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)$ .

0.5

(12,8)

(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)$

(6,4)0.1

(10,3)(11,3) (11,3)(11,4) (11,4)(10,4) (10,4)(10,5) (10,5)(9,5) (9,5)(9,6)

(10,3)0.1 (9,6)0.1

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

(2,6)0.1 (5,5)0.1

Entrada

L’entrada consisteix en diversos casos, cadascun amb $x_1$ , $y_1$ , $x_2$ i $y_2$ , tots entre $-10^8$ i $10^8$ .

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$ .

Information

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