O desafio é, dada uma lista de pontos, classificar de uma maneira que, quando estão conectados nessa ordem, nunca se cruzam.

Formato de entrada (lido em stdin):

X Y
1 2
3 4
5 6
...

A saída deve ser igual à entrada, mas classificada.

Regras:

• Você pode começar de qualquer ponto.
• O último ponto deve ser o mesmo que o primeiro, fazendo um circuito fechado.
• Isso deve ser feito considerando a grade cartesiana.
• Você pode supor que os pontos de entrada nem todos estejam em uma única linha.
• Os pontos finais de cada linha não contam como interseção.

Para mais ajuda:

Mathematica - 20 30 caracteres

Apenas a parte de classificação

SortBy[%, ArcTan @@ # &]

Código de teste completo, que consiste em gerar 100 pontos aleatórios e traçar a linha

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

+26 caracteres

Se você exigir entrada / saída adequada,

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

+2 caracteres

Apenas adicionando N@

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

porque o código acima funciona apenas em números reais e não em números inteiros devido ao comportamento estranho do Mathematica ao classificar expressões simbólicas

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

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

EDIT Acabei de perceber que, se os pontos não estiverem ao redor da origem, não funcionará, por isso também exige mudança para o centro dos pontos

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

A pergunta mudou, portanto, esta resposta contém versões diferentes, com e sem um caminho fechado.

Perl, caminho aberto, 69 bytes

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

Cada ponto é esperado em STDIN como linha, com as coordenadas separadas por espaço em branco.

Qualquer formato numérico é suportado pelo Perl como número (incluindo números de ponto flutuante).

Exemplo:

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

Resultado:

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

Ungolfed:

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

Na versão da primeira pergunta, havia uma conexão entre o último e o primeiro ponto para fazer um circuito.

Centro não existe ponto, 253 bytes

Essa variante pode falhar, se o centro for um dos pontos, veja o exemplo 3.

Editar% s:

• Em sua resposta, swish notou que os pontos devem estar centrados em torno da origem para garantir um circuito sem cruzamentos:

  • A classificação precisa de coordenadas transformadas.
  • A representação original da sequência dos números precisa ser mantida para a saída.

• Correção de bug: o caso especial do eixo x negativo incluía o eixo 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]}<>

Exemplo 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

Saída 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

Exemplo 2:

Teste de representação numérica e transformação de coordenadas.

.9e1 9
7 7.0
8.5 06
7.77 9.45

Saída 2:

7 7.0
8.5 06
.9e1 9
7.77 9.45

Ungolfed:

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

Sem restrição, 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]}<>

Na versão anterior, o centro é colocado no início e os últimos pontos no eixo negativo são classificados na ordem inversa para obter novamente a cruz para o centro. No entanto, isso não é suficiente, porque os últimos pontos podem estar em uma linha diferente. Portanto, o exemplo 3 a seguir falharia.

Isso é corrigido movendo a origem centralizada um pouco para cima e para a direita. Por causa da centralização, deve haver pelo menos um ponto com valor x positivo e um ponto com valor y positivo. Assim, os mínimos dos valores positivos de x e y são tomados e reduzidos a um nono (metade ou terceiro pode ser suficiente). Este ponto não pode ser um dos pontos existentes e é feita a nova origem.

Os tratamentos especiais da origem e o eixo x negativo podem ser removidos, porque existe algum ponto na nova origem.

Exemplo 3:

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

Saída 3:

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

O exemplo 1 agora está classificado de maneira diferente:

Ungolfed:

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 (caminho aberto; 49 caracteres para caminho fechado)

Nota: Esta solução é para a versão atual do desafio , editada por Rusher. É não uma solução válida para o desafio original , que exigia que a linha do último ponto de volta para o primeiro também não deve se cruzam as outras linhas. A solução de 49 caracteres abaixo também é válida para o desafio original.

~]2/$`

O código acima pressupõe que a saída possa estar em qualquer formato razoável. Se o formato de saída precisar corresponder à entrada, a seguinte versão de 13 caracteres fará:

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

Explicação:

• ~avalia a entrada, transformando-a em uma lista de números; ]reúne esses números em uma matriz e 2/divide essa matriz em blocos de dois números, cada um representando um ponto.

• $classifica os pontos em ordem lexicográfica, ou seja, primeiro pela coordenada x e depois, se houver laços, pela coordenada y. É fácil mostrar que isso garantirá que as linhas desenhadas entre os pontos não se cruzem, desde que o caminho não precise voltar ao início.

• Na versão de 5 caracteres, `especifica a matriz classificada, produzindo a representação nativa da sequência (por exemplo [[0 0] [0 4] [4 0] [4 4]]). Na versão mais longa, {" "*n}/junta as coordenadas de cada ponto por um espaço e acrescenta uma nova linha.

Demonstração online: versão curta / versão longa .

Ps. Aqui está uma solução de 49 caracteres para o problema original, em que é necessário fechar o caminho:

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

Funciona de maneira semelhante à solução Perl de Heiko Oberdiek , exceto que, em vez de usar funções trigonométricas, esse código classifica os pontos pela inclinação ( y - y ₀ ) / ( x - x ₀ ), onde ( x ₀ , y ₀ ) é o ponto com o menor coordenado x (e o coordenador y mais baixo , se vários pontos estiverem vinculados ao x mais baixo ).

Como o GolfScript não suporta ponto flutuante, as inclinações são multiplicadas pela constante fixa 9 ⁹ = 387420489. (Se a precisão não for suficiente, você pode substituir o 9com por 99para transformar o multiplicador em 99 ⁹⁹ ≈ 3,7 × 10 ¹⁹⁷ ). algum código extra para romper laços (pela coordenada x ) e garantir que, como na solução de Heiko, os pontos com x = x ₀ sejam classificados por último, em ordem decrescente pela coordenada y .

Novamente, aqui está uma demonstração online .

Mathematica, 35

Isso funciona para QUALQUER lista de pontos únicos.

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

Você diz "read from stdin", então para o Mathematica, eu estou assumindo "read from last output".

Entrada (última saída):

"0 0
4 4
0 4
4 0"

Resultado:

0 0
0 4
4 0
4 4

Se a entrada e a saída não precisarem estar no formato "novas linhas", isso poderá diminuir para 6 caracteres:

Sort@%

tomando a última saída como entrada, assumindo que a última saída seja uma matriz bidimensional.

Entrada (última saída):

{{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);

Ok, admito, o PHP não é a melhor linguagem de golfe, mas tentei.

Aqui está um exemplo de saída:

0000 0000
0000 0004
0004 0000
0004 0004

O que faz é colocar as informações em uma string formatada com zeros anteriores.
Depois, apenas classifica os pontos textualmente.
_{PS Falha nos números acima 9999.}

Python 2.7, 42B

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

Realmente não poderia ser mais simples; leia STDIN, ordene linhas, imprima linhas. NB Respeitei os requisitos exatos de E / S da pergunta, mas se você estiver preenchendo manualmente o STDIN, precisará pressionar CTRL+dpara finalizar a entrada.