El desafío es, dada una lista de puntos, ordenar de una manera que, cuando están conectados en este orden, nunca se crucen.

Formato de entrada (leído desde stdin):

X Y
1 2
3 4
5 6
...

La salida debe ser la misma que la entrada, pero ordenada.

Reglas:

• Puedes comenzar desde cualquier punto.
• El último punto debe ser el mismo que el primero, haciendo un circuito cerrado.
• Debe hacerse teniendo en cuenta la cuadrícula cartesiana.
• Puede suponer que los puntos de entrada no están todos en una sola línea.
• Los puntos finales de cada línea no cuentan como intersección.

Para más ayuda:

Mathematica - 20 30 caracteres

Solo la parte de clasificación

SortBy[%, ArcTan @@ # &]

Código de prueba completo, que consiste en generar 100 puntos aleatorios y trazar la línea

RandomReal[{-10, 10}, {100, 2}];
SortBy[%, ArcTan @@ # &];
ListPlot@% /. 
 Point[p_] :> {EdgeForm[Dashed], FaceForm[White], Polygon[p], 
   PointSize -> Large, Point[p]}

+26 caracteres

Si exige una entrada / salida adecuada, entonces

"0 0
 4 4
 0 4
 4 0";
Grid@SortBy[%~ImportString~"Table", ArcTan @@ # &]

+2 caracteres

Solo agregando N@

Grid@SortBy[%~ImportString~"Table", ArcTan @@ N @ # &]

porque el código anterior solo funciona en números reales y no en enteros debido al comportamiento extraño de Mathematica al ordenar expresiones simbólicas

N@Sort[{ArcTan[1], ArcTan[-2]}]
Sort[N@{ArcTan[1], ArcTan[-2]}]

{0.785398, -1.10715}
{-1.10715, 0.785398}

EDITAR Me acabo de dar cuenta de que si los puntos no están alrededor del origen, no funcionará, por lo que también requiere cambiar al centro de los puntos

SortBy[%, ArcTan @@ N[# - Mean@%] &]

La pregunta ha cambiado, por lo tanto, esta respuesta contiene diferentes versiones, con y sin una ruta cerrada.

Perl, ruta abierta, 69 bytes

print"@$_$/"for sort{$$a[0]<=>$$b[0]||$$a[1]<=>$$b[1]}map{[/\S+/g]}<>

Cada punto se espera en STDIN como línea, con las coordenadas separadas por espacios en blanco.

Se admite cualquier formato de número que Perl interprete como número (incluidos los números de coma flotante).

Ejemplo:

0 0
4 4
0 4
4 0
-2 1
2 -2
2 4
3.21 .56
.035e2 -7.8
0 2

Salida:

-2 1
0 0
0 2
0 4
2 -2
2 4
3.21 .56
.035e2 -7.8
4 0
4 4

Sin golf:

print "@$_$/" for            # print output line      
    sort {                   # sort function for two points $a and $b
        $$a[0] <=> $$b[0]    # compare x part                           
        || $$a[1] <=> $$b[1] # compare y part, if x parts are identical
    }
    map { [/\S+/g] }         # convert input line to point as array reference
    <>                       # read input lines               

Variantes de circuito

En la versión de la primera pregunta, había una conexión entre el último y el primer punto para hacer un circuito.

El centro no es un punto existente, 253 bytes

Esta variante puede fallar, si el centro es uno de los puntos, vea el ejemplo 3.

Ediciones:

• En su respuesta, swish notó que los puntos deben centrarse alrededor del origen para garantizar un circuito libre de cruz:

  • La ordenación necesita coordenadas transformadas.
  • La representación de cadena original de los números debe mantenerse para la salida.

• Corrección de errores: el caso especial para el eje x negativo había incluido el eje x positivo.

print"$$_[2] $$_[3]$/"for sort{($X,$Y)=@$a;($x,$y)=@$b;(!$X&&!$Y?-1:0)||!$x&&!$y||!$Y&&!$y&&$X<0&&$x<0&&$X<=>$x||atan2($Y,$X)<=>atan2($y,$x)||$X**2+$Y**2<=>$x**2+$y**2}map{[$$_[0]-$M/$n,$$_[1]-$N/$n,@$_]}map{$n++;$M+=$$_[0];$N+=$$_[1];$_}map{[/\S+/g]}<>

Ejemplo 1:

4 4
-2 0
2 0
1 1
4 0
-2 -2
-3 -1
1 -2
3 0
2 -4
0 0
-1 -2
3 3
-3 0
2 3
-5 1
-6 -1

Salida 1:

0 0
-6 -1
-3 -1
-2 -2
-1 -2
1 -2
2 -4
2 0
3 0
4 0
1 1
3 3
4 4
2 3
-5 1
-3 0
-2 0

Ejemplo 2

Prueba de representación de números y transformación de coordenadas.

.9e1 9
7 7.0
8.5 06
7.77 9.45

Salida 2:

7 7.0
8.5 06
.9e1 9
7.77 9.45

Sin golf:

print "$$_[2] $$_[3]$/" for sort { # print sorted points
    ($X, $Y) = @$a;                # ($X, $Y) is first point $a
    ($x, $y) = @$b;                # ($x, $y) is second point $b
    (!$X && !$Y ? -1 : 0) ||       # origin comes first, test for $a
    !$x && !$y ||                  # origin comes first, test for $b
    !$Y && !$y && $X < 0 && $x < 0 && $X <=> $x ||
        # points on the negative x-axis are sorted in reverse order
    atan2($Y, $X) <=> atan2($y, $x) ||
        # sort by angles; the slope y/x would be an alternative,
        # then the x-axis needs special treatment
    $X**2 + $Y**2 <=> $x**2 + $y**2
        # the (quadratic) length is the final sort criteria
}
map { [ # make tuple with transformed and original coordinates
        # the center ($M/$n, $N/$n) is the new origin
        $$_[0] - $M/$n,  # transformed x value
        $$_[1] - $N/$n,  # transformed y value
        @$_              # original coordinates
] }
map {
    $n++;                # $n is number of points
    $M += $$_[0];        # $M is sum of x values
    $N += $$_[1];        # $N is sum of y values
    $_                   # pass orignal coordinates through
}
map {                    # make tuple with point coordinates
    [ /\S+/g ]           # from non-whitespace in input line
}
<>                       # read input lines

Sin restricción, 325 bytes

print"$$_[2] $$_[3]$/"for sort{($X,$Y)=@$a;($x,$y)=@$b;atan2($Y,$X)<=>atan2($y,$x)||$X**2+$Y**2<=>$x**2+$y**2}map{[$$_[0]-$O/9,$$_[1]-$P/9,$$_[2],$$_[3]]}map{$O=$$_[0]if$$_[0]>0&&($O>$$_[0]||!$O);$P=$$_[1]if$$_[1]>0&&($P>$$_[1]||!$P);[@$_]}map{[$$_[0]-$M/$n,$$_[1]-$N/$n,@$_]}map{$n++;$M+=$$_[0];$N+=$$_[1];$_}map{[/\S+/g]}<>

En la versión anterior, el centro se coloca al principio y los últimos puntos en el eje negativo se ordenan en orden inverso para volver a cruzarse al centro nuevamente. Sin embargo, esto no es suficiente, porque los últimos puntos podrían estar en una línea diferente. Así, el siguiente ejemplo 3 fallaría.

Esto se soluciona moviendo el origen centrado un poco hacia arriba y hacia la derecha. Debido al centrado, debe haber al menos un punto con valor x positivo y un punto con valor y positivo. Por lo tanto, se toman los mínimos de los valores positivos x e y y se reducen a un noveno (medio o tercero podría ser suficiente). Este punto no puede ser uno de los puntos existentes y se convierte en el nuevo origen.

Los tratamientos especiales del origen y el eje x negativo se pueden eliminar, porque hay algún punto que se encuentra en el nuevo origen.

Ejemplo 3

-2 -2
-1 -1
-2 2
-1 1
2 -2
1 -1
2 2
1 1
0 0

Salida 3:

0 0
-1 -1
-2 -2
1 -1
2 -2
1 1
2 2
-2 2
-1 1

El ejemplo 1 ahora está ordenado de manera diferente:

Sin golf:

print "$$_[2] $$_[3]$/" for sort { # print sorted points        
    ($X, $Y) = @$a;                # ($X, $Y) is first point $a 
    ($x, $y) = @$b;                # ($x, $y) is second point $b
    atan2($Y, $X) <=> atan2($y, $x) ||
        # sort by angles; the slope y/x would be an alternative,
        # then the x-axis needs special treatment
    $X**2 + $Y**2 <=> $x**2 + $y**2
        # the (quadratic) length is the final sort criteria
}  
map { [ # make tuple with transformed coordinates
    $$_[0] - $O/9, $$_[1] - $P/9,  # new transformed coordinate
    $$_[2],  $$_[3]                # keep original coordinate
] }
map {
    # get the minimum positive x and y values 
    $O = $$_[0] if $$_[0] > 0 && ($O > $$_[0] || !$O);         
    $P = $$_[1] if $$_[1] > 0 && ($P > $$_[1] || !$P);
    [ @$_ ]               # pass tuple through
}
map { [ # make tuple with transformed and original coordinates
        # the center ($M/$n, $N/$n) is the new origin
        $$_[0] - $M/$n,  # transformed x value
        $$_[1] - $N/$n,  # transformed y value 
        @$_              # original coordinates
] }  
map {
    $n++;                # $n is number of points
    $M += $$_[0];        # $M is sum of x values 
    $N += $$_[1];        # $N is sum of y values
    $_                   # pass orignal coordinates through
}
map {                    # make tuple with point coordinates
    [ /\S+/g ]           # from non-whitespace in input line
} 
<>                       # read input lines

GolfScript, 6/13 caracteres (ruta abierta; 49 caracteres para ruta cerrada)

Nota: Esta solución es para la versión actual del desafío editado por Rusher. Es no una solución válida a la original desafío , que requiere que la línea de atrás último punto al primer tampoco está cortado por las otras líneas. La solución de 49 caracteres a continuación también es válida para el desafío original.

~]2/$`

El código anterior supone que la salida puede estar en cualquier formato razonable. Si el formato de salida tiene que coincidir con la entrada, la siguiente versión de 13 caracteres funcionará:

~]2/${" "*n}/

Explicación:

• ~evalúa la entrada, convirtiéndola en una lista de números; ]reúne estos números en una matriz y 2/divide esta matriz en bloques de dos números, cada uno representando un punto.

• $clasifica los puntos en orden lexicográfico, es decir, primero por la coordenada x y luego, si hay vínculos, por la coordenada y. Es fácil demostrar que esto garantizará que las líneas dibujadas entre los puntos no se crucen, siempre que la ruta no necesite volver al principio.

• En la versión de 5 caracteres, `stringifica la matriz ordenada, produciendo la representación de cadena nativa de la misma (por ejemplo [[0 0] [0 4] [4 0] [4 4]]). En la versión más larga, {" "*n}/une las coordenadas de cada punto por un espacio y agrega una nueva línea.

Demostración en línea: versión corta / versión larga .

PD. Aquí hay una solución de 49 caracteres para el problema original, donde se debe cerrar la ruta:

~]2/$.0=~:y;:x;{~y-\x-.+.@9.?*@(/\.!@@]}${" "*n}/

Funciona de manera similar a la solución Perl de Heiko Oberdiek , excepto que, en lugar de usar funciones trigonométricas, este código ordena los puntos por la pendiente ( y - y ₀ ) / ( x - x ₀ ), donde ( x ₀ , y ₀ ) es el punto con la menor coordenada x (y la menor coordenada y , si varios puntos están empatados para la x más baja ).

Dado que GolfScript no admite coma flotante, las pendientes se multiplican por la constante fija 9 ⁹ = 387420489. (Si eso no es suficiente precisión, puede reemplazarlo 9con 99para convertir el multiplicador en 99 ⁹⁹ ≈ 3.7 × 10 ¹⁹⁷ ). También hay algún código extra para romper los lazos (por la coordenada x ) y para asegurar que, como en la solución de Heiko, los puntos con x = x ₀ se ordenan al final, en orden decreciente por coordenada y .

Nuevamente, aquí hay una demostración en línea .

Mathematica, 35

Esto funciona para CUALQUIER lista de puntos únicos.

s=StringSplit;Grid@Sort@s@s[%,"\n"]

Dices "leer desde stdin", así que para Mathematica, estoy asumiendo "leer desde la última salida".

Entrada (última salida):

"0 0
4 4
0 4
4 0"

Salida:

0 0
0 4
4 0
4 4

Si la entrada y la salida no necesitan estar en el formato de "nuevas líneas", esto puede reducirse a 6 caracteres:

Sort@%

tomando la última salida como entrada, suponiendo que la última salida es una matriz bidimensional.

Entrada (última salida):

{{0,0},{4,4},{0,4},{4,0}}

Ouput:

{{0,0},{0,4},{4,0},{4,4}}

PHP (175 109 100 caracteres)

while(fscanf(STDIN,'%d%d',$a,$b))$r[]=sprintf('%1$04d %2$04d',$a,$b);sort($r);echo implode('
',$r);

Bien, lo admito, PHP no es el mejor lenguaje de golf, pero lo probé.

Aquí hay algunos resultados de muestra:

0000 0000
0000 0004
0004 0000
0004 0004

Lo que hace es poner la información en una cadena formateada con ceros anteriores.
Luego solo ordena los puntos textualmente.
_{PD: falla en los números anteriores 9999.}

Python 2.7, 42B

import sys
print''.join(sorted(sys.stdin))

Realmente no podría ser más simple; leer STDIN, ordenar líneas, imprimir líneas. Nota: he respetado los requisitos exactos de E / S de la pregunta, pero si está completando manualmente STDIN, debe presionar CTRL+dpara finalizar la entrada.