fundo

Você é um rico executivo de um império de software. Seu tempo vale muito dinheiro. Como tal, você deve sempre viajar na rota mais eficiente possível. No entanto, como executivo, você passa muito tempo participando de importantes ligações telefônicas. É fundamental que você nunca interrompa as ligações, portanto nunca deve viajar por áreas que não possuem serviço de celular!

O desafio

Você receberá uma lista de três tuplas, cada uma representando a localização e a potência de uma torre de celular. Como exemplo, [50, 25, 16]representaria uma torre de célula localizada em <x,y> = <50, 25>com um círculo de raio 16 representando seu círculo de influência. Com essa lista em mente, você deve viajar da posição inicial <0, 0>até o destino em <511, 511>, na menor distância possível, sem perder o serviço da célula. Isso é código-golfe , então o código mais curto vence!

Entrada / Saída

Você é livre para manipular a entrada em um formato que facilite a leitura, como em um arquivo ou como uma matriz aninhada usando STDIN eval, etc. Você pode codificar a entrada, desde que seu código funcione para outras entradas como bem. Os caracteres exatos usados ​​para codificar permanentemente a entrada não serão contados, mas o nome da variável e os caracteres de atribuição serão contados. Você não deve assumir que a entrada está em uma ordem específica ou que toda torre de célula é relevante para o problema. Se você tiver alguma dúvida, por favor, deixe um comentário e tentarei esclarecê-lo.

A saída deve ser uma lista de coordenadas, marcando pontos que, quando conectados, formam um caminho para a saída. A precisão só precisa ser arredondada para o número inteiro mais próximo e, se você estiver 1-2 unidades fora do que eu tenho em mim, exemplo de saída, tudo bem. Incluí imagens abaixo para esclarecer isso.

Boa sorte!

Exemplos

input:
[ 32,  42,  64]
[112,  99,  59]
[141, 171,  34]
[157, 191,  28]
[177, 187,  35]
[244, 168,  57]
[289, 119,  20]
[299, 112,  27]
[354,  59,  58]
[402,  98,  23]
[429,  96,  29]
[424, 145,  34]
[435, 146,  20]
[455, 204,  57]
[430, 283,  37]
[432, 306,  48]
[445, 349,  52]
[424, 409,  59]
[507, 468,  64]

output:
0 0
154 139
169 152
189 153
325 110
381 110
400 120
511 511

input2
[ 32,  42,  64]
[112,  99,  59]
[141, 171,  34]
[157, 191,  28]
[177, 187,  35]
[244, 168,  57]
[289, 119,  20]
[299, 112,  27]
[354,  59,  58]
[402,  98,  23]
[429,  96,  29]
[424, 145,  34]
[435, 146,  20]
[455, 204,  57]
[430, 283,  37]
[432, 306,  48]
[445, 349,  52]
[424, 409,  59]
[507, 468,  64]
[180, 230,  39]
[162, 231,  39]
[157, 281,  23]
[189, 301,  53]
[216, 308,  27]
[213, 317,  35]
[219, 362,  61]
[242, 365,  42]
[288, 374,  64]
[314, 390,  53]
[378, 377,  30]
[393, 386,  34]

output2:
0 0
247 308
511 511

O caminho anterior é destacado em azul, mas você pode ver que a adição de mais torres permite uma rota mais ideal.

Python, 1.291 1.271 1.225 bytes

Como Martin observou, esse problema pode ser amplamente reduzido ao seu excelente desafio com elásticos . Usando a terminologia desse desafio, podemos tomar como segundo conjunto de pregos os pontos de interseção entre os círculos no limite da área fechada:

Como elástico, podemos seguir qualquer caminho P entre os dois pontos de extremidade que são executados dentro da área fechada. Podemos então invocar uma solução para o problema do elástico para produzir um caminho mínimo (localmente). O desafio é, é claro, encontrar esse caminho P , ou mais precisamente, encontrar o suficiente caminhos para que pelo menos um deles produza o caminho globalmente mínimo (observe que, no primeiro caso de teste, precisamos de pelo menos um caminho para abranja todas as possibilidades e, no segundo caso de teste, pelo menos duas.)

Uma abordagem ingênua seria apenas tentar todos os caminhos possíveis: para cada sequência de círculos adjacentes (que se cruzam) que conecta os dois pontos finais, siga o caminho ao longo de seus centros (quando dois círculos se cruzam, o segmento entre seus centros está sempre dentro de sua união). .) Embora essa abordagem seja tecnicamente correta, ela pode levar a um número ridiculamente grande de caminhos. Enquanto eu era capaz de resolver o primeiro caso de teste usando essa abordagem em alguns segundos, o segundo demorou uma eternidade. Ainda assim, podemos tomar esse método como ponto de partida e tentar minimizar o número de caminhos que temos para testar. Isto é o que se segue.

Construímos nossos caminhos executando basicamente uma pesquisa profunda no gráfico de círculos. Estamos procurando uma maneira de eliminar possíveis rotas de pesquisa em cada etapa da pesquisa.

Suponha que em algum momento estamos no círculo A , que possui dois círculos adjacentes B e C , que também são adjacentes um ao outro. Podemos ir de A a C visitando B (e vice-versa), para que possamos pensar que visitar B e C diretamente de A é desnecessário. Infelizmente, isso está errado, pois esta ilustração mostra:

Se os pontos na ilustração são os dois pontos finais, podemos ver que, passando de A a C a B , obtemos um caminho mais longo.

Que tal esse: se estamos testando os movimentos A → B e A → C , não é necessário testar A → B → C ou A → C → B , pois eles não podem resultar em caminhos mais curtos. Errado de novo:

O ponto é que o uso de argumentos puramente baseados em adjacência não será suficiente; nós temos que usar a geometria do problema também. O que os dois exemplos acima têm em comum (assim como o segundo caso de teste em uma escala maior) é que há um "buraco" na área fechada. Ela se manifesta no fato de que alguns dos pontos de intersecção na fronteira - nossas "unhas" - estão dentro do triângulo. ABC cujos vértices são os centros dos círculos:

Quando isso acontece, há uma chance de que ir de A a B e de A a C resulte em caminhos diferentes. Mais importante, quando isso não acontece (ou seja, se não houvesse uma lacuna entre A , B e C ), é garantido que todos os caminhos que começam com A → B → C e com A → C e que são equivalentes resultarão no mesmo caminho localmente mínimo, portanto, se visitarmos B , também não precisaremos visitar C diretamente de A .

Isso nos leva ao nosso método de eliminação: quando estamos no círculo A , mantemos uma lista H dos círculos adjacentes que visitamos. Esta lista está inicialmente vazia. Visitamos um círculo adjacente B se houver "pregos" em todos os triângulos formados pelos centros de A , B e qualquer um dos círculos em H adjacente a B . Esse método reduz drasticamente o número de caminhos que precisamos testar para apenas 1 no primeiro caso de teste e 10 no segundo.

Mais algumas notas:

• É possível diminuir ainda mais o número de caminhos que testamos, mas esse método é bom o suficiente para a escala desse problema.

• Eu usei o algoritmo de minha solução para o desafio do elástico. Como esse algoritmo é incremental, ele pode ser facilmente integrado ao processo de localização de caminhos, para minimizar o caminho à medida que avançamos. Como muitos caminhos compartilham um segmento inicial, isso pode melhorar significativamente o desempenho quando temos muitos caminhos. Também pode prejudicar o desempenho se houver muito mais becos sem saída do que caminhos válidos. De qualquer maneira, para os casos de teste fornecidos, executar o algoritmo para cada caminho separadamente é bom o suficiente.

• Há um caso de aresta em que essa solução pode falhar: se algum dos pontos no limite for o ponto de interseção de dois círculos tangentes, em algumas condições, o resultado poderá estar errado. Isso se deve à maneira como o algoritmo de elástico funciona. Com algumas modificações, é possível lidar com esses casos também, mas, diabos, já é tempo suficiente.

# First test case
I={((32.,42.),64.),((112.,99.),59.),((141.,171.),34.),((157.,191.),28.),((177.,187.),35.),((244.,168.),57.),((289.,119.),20.),((299.,112.),27.),((354.,59.),58.),((402.,98.),23.),((429.,96.),29.),((424.,145.),34.),((435.,146.),20.),((455.,204.),57.),((430.,283.),37.),((432.,306.),48.),((445.,349.),52.),((424.,409.),59.),((507.,468.),64.)}
# Second test case
#I={((32.,42.),64.),((112.,99.),59.),((141.,171.),34.),((157.,191.),28.),((177.,187.),35.),((244.,168.),57.),((289.,119.),20.),((299.,112.),27.),((354.,59.),58.),((402.,98.),23.),((429.,96.),29.),((424.,145.),34.),((435.,146.),20.),((455.,204.),57.),((430.,283.),37.),((432.,306.),48.),((445.,349.),52.),((424.,409.),59.),((507.,468.),64.),((180.,230.),39.),((162.,231.),39.),((157.,281.),23.),((189.,301.),53.),((216.,308.),27.),((213.,317.),35.),((219.,362.),61.),((242.,365.),42.),((288.,374.),64.),((314.,390.),53.),((378.,377.),30.),((393.,386.),34.)}

from numpy import*
V=array;X=lambda u,v:u[0]*v[1]-u[1]*v[0];L=lambda v:dot(v,v)
e=V([511]*2)
N=set()
for c,r in I:
 for C,R in I:
  v=V(C)-c;d=L(v)
  if d:
    a=(r*r-R*R+d)/2/d;q=r*r/d-a*a
    if q>=0:w=V(c)+a*v;W=V([-v[1],v[0]])*q**.5;N|={tuple(t)for t in[w+W,w-W]if all([L(t-T)>=s**2-1e-9 for T,s in I])}
N=map(V,N)
def T(a,b,c,p):H=[X(p-a,b-a),X(p-b,c-b),X(p-c,a-c)];return min(H)*max(H)>=0
def E(a,c,b):
 try:d=max((X(n-a,b-a)**2,id(n),n)for n in N if T(a,b,c,n)*X(n-b,c-b)*X(n-c,a-c))[2];A=E(a,c,d);B=E(d,c,b);return[A[0]+[d]+B[0],A[1]+[sign(X(c-a,b-c))]+B[1]]
 except:return[[]]*2
def P(I,c,r,A):
 H=[];M=[""]
 if L(c-e)>r*r:
    for C,R in I:
     if L(C-c)<=L(r+R)and all([L(h-C)>L(R+s)or any([T(c,C,h,p)for p in N])for h,s in H]):v=V(C);H+=[(v,R)];M=min(M,P(I-{(C,R)},v,R,A+[v]))
    return M
 A+=[e]*2;W=[.5]*len(A)
 try:
  while 1:
    i=[w%1*2or w==0for w in W[2:-2]].index(1);u,a,c,b,v=A[i:i+5];A[i+2:i+3],W[i+2:i+3]=t,_=E(a,c,b);t=[a]+t+[b]
    for p,q,j,k in(u,a,1,i+1),(v,b,-2,i+len(t)):x=X(q-p,c-q);y=X(q-p,t[j]-q);z=X(c-q,t[j]-q);d=sign(j*z);W[k]+=(x*y<=0)*(x*z<0 or y*z>0)*(x!=0 or d*W[k]<=0)*(y!=0 or d*W[k]>=0)*d
 except:return[sum(L(A[i+1]-A[i])**.5for i in range(len(A)-1)),id(A),A]
print V(P(I,e*0,0,[e*0]*2)[2][1:-1])

A entrada é fornecida através da variável Icomo um conjunto de tuplas, ((x, y), r)onde (x, y)é o centro do círculo e rseu raio. Os valores devem ser floats, nãoint s. O resultado é impresso em STDOUT.

Exemplo

# First test case
I={((32.,42.),64.),((112.,99.),59.),((141.,171.),34.),((157.,191.),28.),((177.,187.),35.),((244.,168.),57.),((289.,119.),20.),((299.,112.),27.),((354.,59.),58.),((402.,98.),23.),((429.,96.),29.),((424.,145.),34.),((435.,146.),20.),((455.,204.),57.),((430.,283.),37.),((432.,306.),48.),((445.,349.),52.),((424.,409.),59.),((507.,468.),64.)}

[[   0.            0.        ]
 [ 154.58723733  139.8329183 ]
 [ 169.69950891  152.76985495]
 [ 188.7391093   154.02738541]
 [ 325.90536774  109.74141936]
 [ 382.19108518  109.68789517]
 [ 400.00362897  120.91319495]
 [ 511.          511.        ]]