F006B. Distància de Manhattan P64555


Statement
 

pdf   zip

thehtml

La distància de Manhattan entre dos punts amb coordenades enteres en el pla es defineix com el nombre de passos unitaris cap amunt, avall, esquerra o dreta que cal fer per anar d’un punt a l’altre. (Té aquest nom perquè és el nombre d’illes que cal caminar en un barri quadricular per anar d’un encreuament a un altre.)

Per exemple, considereu el punt (1, -2) de la figura de la dreta (el més gros). El punt més proper és el (2, -3), que es troba a distància 2. El punt més llunyà és el (-2, 1), que es troba a distància 6. Excepte el (2, 2), la resta de punts es troben a distància 4.

Feu un programa que, donat un punt (x, y) i n punts (x1, y1), …, (xn, yn), escrigui aquests punts ordenats en funció de la seva distància de Manhattan a (x, y).

(205, 230)(-85, -140) (-80, 0)(1, 0)200 (115, 5)x (0, -140)(0, 1)200 (5, 55)y

(-80, -2)(0, 1)4 (-60, -2)(0, 1)4 (-40, -2)(0, 1)4 (-20, -2)(0, 1)4 (20, -2)(0, 1)4 (40, -2)(0, 1)4 (60, -2)(0, 1)4 (80, -2)(0, 1)4 (100, -2)(0, 1)4

(-2, -140)(1, 0)4 (-2, -120)(1, 0)4 (-2, -100)(1, 0)4 (-2, -80)(1, 0)4 (-2, -60)(1, 0)4 (-2, -40)(1, 0)4 (-2, -20)(1, 0)4 (-2, 20)(1, 0)4 (-2, 40)(1, 0)4

(20, -40)6 (25, -43)(1, -2) (40, -60)4 (45, -63)(2, -3) (20, -120)4 (25, -123)(1, -6) (100, -40)4 (105, -43)(5, -2) (-60, -40)4 (-55, -43)(-3, -2) (-40, -20)4 (-35, -23)(-2, -1) (-40, 20)4 (-53, 25)(-2, 1) (40, 40)4 (45, 37)(2, 2) (60, 0)4 (47, 5)(3, 0)

(20, -45)(0, -1)4 (20, -51)(0, -1)4 (20, -57)(0, -1)3 (20, -60)(1, 0)3 (25, -60)(1, 0)4 (31, -60)(1, 0)4

(20, 20)(0, -1)4 (20, 14)(0, -1)4 (20, 8)(0, -1)4 (20, 2)(0, -1)4 (20, -4)(0, -1)4 (20, -10)(0, -1)4 (20, -16)(0, -1)4 (20, -22)(0, -1)4 (20, -28)(0, -1)4 (20, -34)(0, -1)2

(20, 20)(-1, 0)4 (14, 20)(-1, 0)4 (8, 20)(-1, 0)4 (2, 20)(-1, 0)4 (-4, 20)(-1, 0)4 (-10, 20)(-1, 0)4 (-16, 20)(-1, 0)4 (-22, 20)(-1, 0)4 (-28, 20)(-1, 0)4 (-34, 20)(-1, 0)2

Entrada

L’entrada consisteix només en nombres enters, i està formada per una línia amb x i y, una línia amb n, i per una o més línies amb les coordenades dels n punts: x1, y1, x2, y2, …, xn, yn. Podeu suposar 0 ≤ n ≤ 105. Els n punts són tots diferents, i venen donats en qualsevol ordre.

Sortida

Escriviu els n punts agrupats segons la seva distància a (x, y). Si dos punts es troben a la mateixa distància, cal escriure primer aquell que tingui la primera coordenada més petita i, en cas d’empat, el que tingui la segona coordenada més petita. Seguiu el format dels exemples.

Observació

El vostre algorisme ha de ser eficient en tots els casos, perquè n pot ser gran, i perquè els jocs de proves privats inclouran casos límit com ara molts punts a la mateixa distància.

Public test cases
  • Input

    1 -2
    8
    -3 -2
    -2 -1
    -2  1
    1 -6
    2 -3
    2  2
    3  0
    5 -2
    

    Output

    punts a distancia 2
    2 -3
    punts a distancia 4
    -3 -2
    -2 -1
    1 -6
    3 0
    5 -2
    punts a distancia 5
    2 2
    punts a distancia 6
    -2 1
    
  • Input

    2 2
    13
                2 4
          1 3   2 3   3 3
    0 2   1 2   2 2   3 2   4 2
          1 1   2 1   3 1
                2 0
    

    Output

    punts a distancia 0
    2 2
    punts a distancia 1
    1 2
    2 1
    2 3
    3 2
    punts a distancia 2
    0 2
    1 1
    1 3
    2 0
    2 4
    3 1
    3 3
    4 2
    
  • Input

    -100000000 -100000000
    4
    -1 -1
    0 0
    50000000 50000000
    -87654321 87654321
    

    Output

    punts a distancia 199999998
    -1 -1
    punts a distancia 200000000
    -87654321 87654321
    0 0
    punts a distancia 300000000
    50000000 50000000
    
  • Input

    2 3
    0
    

    Output

    
            
                                
  • Information
    Author
    Professorat de P1
    Language
    Catalan
    Other languages
    English
    Official solutions
    C++
    User solutions
    C++