tło

Jesteś bogatym wykonawcą imperium oprogramowania. Twój czas jest wart dużo pieniędzy. Jako taki, musisz zawsze podróżować możliwie najbardziej wydajną trasą. Jednak jako dyrektor spędzasz dużo czasu uczestnicząc w ważnych rozmowach telefonicznych. Najważniejsze jest, aby nigdy nie odrzucać połączeń, więc nigdy nie wolno podróżować przez obszary, które nie mają sieci komórkowej!

Wyzwanie

Otrzymasz listę trzech krotek, z których każda reprezentuje lokalizację i moc wieży komórkowej. Jako przykład [50, 25, 16]reprezentuje wieżę komórkową umieszczoną w <x,y> = <50, 25>okręgu o promieniu 16 reprezentującym jej koło wpływów. Mając na uwadze tę listę, musisz podróżować z pozycji początkowej w miejscu <0, 0>docelowym <511, 511>w możliwie najkrótszej odległości bez utraty usługi komórkowej. To jest golf golfowy , więc wygrywa najkrótszy kod!

Wejście wyjście

Możesz dowolnie manipulować danymi wejściowymi w formie ułatwiającej czytanie, np. W pliku lub jako zagnieżdżoną tablicę za pomocą STDIN przy użyciu evalitp. Możesz zakodować dane wejściowe na stałe, o ile kod działa dla innych danych wejściowych, takich jak dobrze. Dokładne znaki użyte do zakodowania wejścia nie zostaną policzone, ale nazwa zmiennej i znaki przypisania będą. Nie należy zakładać, że dane wejściowe są w określonej kolejności lub że każda wieża komórkowa jest odpowiednia do problemu. Jeśli masz jakieś pytania, zostaw komentarz, a ja postaram się wyjaśnić.

Wyjście ma być listą współrzędnych, oznaczającą punkty, które po połączeniu w celu utworzenia ścieżki do wyjścia. Dokładność wystarczy zaokrąglić do najbliższej liczby całkowitej, a jeśli jesteś o 1-2 jednostki od tego, co mam w przykładzie wyjściowym, to dobrze. Poniżej wyjaśniam zdjęcia.

Powodzenia!

Przykłady

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

Poprzednia ścieżka jest podświetlona na niebiesko, ale można zobaczyć, że dodanie większej liczby wież pozwala na bardziej optymalną trasę.

Pyton, 1 291 1 271 1,225 bajtów

Jak zauważył Martin, problem ten można w dużej mierze zredukować do jego doskonałego wyzwania dla gumki . Używając terminologii tego wyzwania, możemy przyjąć jako drugi zestaw gwoździ punkty przecięcia okręgów na granicy zamkniętego obszaru:

Jako gumka możemy obrać dowolną ścieżkę P między dwoma punktami końcowymi, która biegnie wewnątrz zamkniętego obszaru. Możemy następnie przywołać rozwiązanie problemu gumki, aby stworzyć (lokalnie) minimalną ścieżkę. Wyzwanie polega oczywiście na znalezieniu takiej ścieżki P , a dokładniej, znalezieniu wystarczającej liczby ścieżek, aby co najmniej jedna z nich tworzyła globalnie minimalną ścieżkę (zauważ, że w pierwszym przypadku testowym potrzebujemy co najmniej jednej ścieżki do obejmują wszystkie możliwości, aw drugim przypadku co najmniej dwa).

Naiwnym podejściem byłoby po prostu wypróbowanie wszystkich możliwych ścieżek: dla każdej sekwencji sąsiednich (tj. Przecinających się) okręgów, które łączą dwa punkty końcowe, poprowadź ścieżkę wzdłuż ich środków (gdy dwa koła się przecinają, segment między ich środkami zawsze znajduje się w obrębie ich związku .) Chociaż takie podejście jest technicznie poprawne, może prowadzić do absurdalnie dużej liczby ścieżek. Podczas gdy byłem w stanie rozwiązać pierwszy przypadek testowy przy użyciu tego podejścia w ciągu kilku sekund, drugi trwał wieczność. Mimo to możemy potraktować tę metodę jako punkt wyjścia i spróbować zminimalizować liczbę ścieżek, które musimy przetestować. Oto co następuje.

Nasze ścieżki budujemy w zasadzie, przeprowadzając najpierw głębokość wyszukiwania na wykresie okręgów. Szukamy sposobu na wyeliminowanie potencjalnych kierunków wyszukiwania na każdym etapie wyszukiwania.

Załóżmy, że w pewnym momencie jesteśmy w kręgu A , który ma dwa sąsiednie koła B i C , które również sąsiadują ze sobą. Możemy dostać się od A do C , odwiedzając B (i odwrotnie), więc możemy pomyśleć, że odwiedzanie zarówno B, jak i C bezpośrednio z A jest niepotrzebne. Niestety jest to błędne, jak pokazuje ta ilustracja:

Jeśli punkty na ilustracji są dwoma punktami końcowymi, możemy zobaczyć, że przechodząc od A do C przez B , otrzymujemy dłuższą ścieżkę.

Co powiesz na to: jeśli testujemy oba ruchy A → B i A → C , to nie jest konieczne testowanie A → B → C lub A → C → B , ponieważ nie mogą one skutkować krótszymi ścieżkami. Znowu źle:

Chodzi o to, że użycie argumentów opartych wyłącznie na przyleganiu nie ma zamiaru go wyciąć; musimy również użyć geometrii problemu. To, co łączy dwa powyższe przykłady (podobnie jak drugi przypadek testowy na większą skalę), polega na tym, że w zamkniętym obszarze znajduje się „dziura”. Przejawia się to w tym, że niektóre punkty przecięcia na granicy - nasze „gwoździe” - znajdują się w trójkącie △ ABC, którego wierzchołki są środkami okręgów:

Kiedy tak się stanie, istnieje szansa, że ​​przejście z A do B i z A do C spowoduje różne ścieżki. Co ważniejsze, jeśli tak się nie stanie (tj. Jeśli nie będzie przerwy między A , B i C ), to gwarantuje się, że wszystkie ścieżki zaczynające się od A → B → C i A → C, które w przeciwnym razie są równoważne, będą skutkować w tym samym lokalnie minimalnej ścieżki, stąd jeśli odwiedzimy B nie trzeba również odwiedzić C bezpośrednio z A .

To prowadzi nas do naszej metody eliminacji: kiedy jesteśmy w kręgu A , trzymamy listę H sąsiednich kręgów, które odwiedziliśmy. Ta lista jest początkowo pusta. Odwiedzimy sąsiedniego okręgu B , jeśli istnieją jakieś „paznokcie” w każdym z trójkątów utworzonych przez centra A , B i każdy z kręgów H przylegających do B . Ta metoda dramatycznie obniża liczbę ścieżek, które musimy przetestować, do zaledwie 1 w pierwszym przypadku testowym i 10 w drugim.

Jeszcze kilka notatek:

• Można jeszcze bardziej zmniejszyć liczbę testowanych ścieżek, ale ta metoda jest wystarczająca dla skali tego problemu.

• Użyłem algorytmu od mojego rozwiązania do wyzwania gumki. Ponieważ ten algorytm ma charakter przyrostowy, można go dość łatwo zintegrować z procesem znajdowania ścieżki, aby zminimalizować ścieżkę w miarę postępów. Ponieważ wiele ścieżek ma wspólny segment początkowy, może to znacznie poprawić wydajność, gdy mamy wiele ścieżek. Może również zaszkodzić wydajności, jeśli jest znacznie więcej ślepych uliczek niż prawidłowe ścieżki. Tak czy inaczej, dla danych przypadków testowych wykonanie algorytmu dla każdej ścieżki osobno jest wystarczające.

• Jest jeden przypadek krawędzi, w którym to rozwiązanie może się nie powieść: jeśli którykolwiek z punktów na granicy jest punktem przecięcia dwóch stycznych okręgów, to w pewnych warunkach wynik może być błędny. Wynika to ze sposobu działania algorytmu gumki. Z pewnymi modyfikacjami można również obsługiwać te przypadki, ale do diabła, to już wystarczająco długo.

# 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])

Dane wejściowe są podawane przez zmienną Ijako zbiór krotek, w ((x, y), r)których (x, y)znajduje się środek okręgu i rjego promień. Wartości muszą być floats, inta nie s. Wynik zostanie wydrukowany do STDOUT.

Przykład

# 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.        ]]