Latar Belakang

Anda adalah eksekutif kaya kerajaan perangkat lunak. Waktu Anda bernilai banyak uang. Karena itu, Anda harus selalu bepergian dengan rute seefisien mungkin. Namun, sebagai seorang eksekutif, Anda menghabiskan banyak waktu untuk berpartisipasi dalam panggilan telepon penting. Sangat penting bagi Anda untuk tidak pernah menelepon, jadi Anda tidak boleh bepergian melalui area yang tidak memiliki layanan seluler!

Tantangan

Anda akan diberikan daftar tiga tupel, yang masing-masing mewakili lokasi dan kekuatan menara sel. Sebagai contoh, [50, 25, 16]akan mewakili menara sel yang terletak di <x,y> = <50, 25>dengan lingkaran jari-jari 16 yang mewakili lingkaran pengaruhnya. Dengan mengingat daftar ini, Anda harus melakukan perjalanan dari posisi awal <0, 0>Anda ke tujuan di <511, 511>, dalam jarak sesingkat mungkin tanpa kehilangan layanan seluler. Ini kode-golf , jadi kode terpendek menang!

Input output

Anda bebas untuk memanipulasi input ke dalam bentuk yang membuatnya mudah dibaca, seperti dalam file, atau sebagai array bersarang melalui STDIN menggunakan eval, dll. Anda dapat mengubah kode input, selama kode Anda berfungsi untuk input lain seperti baik. Karakter persis yang digunakan untuk memasukkan kode tidak akan dihitung, tetapi nama variabel dan karakter penugasan akan dihitung. Anda tidak boleh berasumsi bahwa input dalam urutan tertentu, atau bahwa setiap menara sel relevan dengan masalah. Jika Anda memiliki pertanyaan, silakan tinggalkan komentar dan saya akan mencoba menjelaskannya.

Outputnya menjadi daftar koordinat, menandai titik-titik yang ketika terhubung agar membentuk jalur ke pintu keluar. Akurasi hanya perlu dibulatkan ke bilangan bulat terdekat, dan jika Anda 1-2 unit dari apa yang saya miliki dalam output saya contoh, itu baik-baik saja. Saya telah menyertakan gambar di bawah ini untuk menjelaskan hal ini.

Semoga berhasil!

Contohnya

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

Jalur sebelumnya disorot dengan warna biru, tetapi Anda bisa melihat penambahan lebih banyak menara memungkinkan rute yang lebih optimal.

Python, 1.291 1.271 1.225 byte

Seperti yang dicatat Martin, masalah ini sebagian besar dapat dikurangi menjadi tantangan karet gelangnya yang sangat bagus . Menggunakan terminologi tantangan itu, kita dapat mengambil sebagai set kedua paku titik-titik persimpangan antara lingkaran pada batas area terlampir:

Sebagai karet gelang, kita dapat mengambil jalur P antara dua titik akhir yang membentang di dalam area tertutup. Kami kemudian dapat meminta solusi untuk masalah karet gelang untuk menghasilkan jalur minimal (lokal). Tantangannya adalah, tentu saja, untuk menemukan jalur P , atau lebih tepatnya, untuk menemukan jalur yang cukup sehingga setidaknya satu dari mereka menghasilkan jalur minimal global (perhatikan bahwa dalam uji-kasus pertama kita membutuhkan setidaknya satu jalur untuk mencakup semua kemungkinan, dan dalam kasus uji kedua setidaknya dua.)

Pendekatan naif adalah dengan hanya mencoba semua jalur yang mungkin: Untuk setiap urutan lingkaran yang berdekatan (yaitu berpotongan) yang menghubungkan dua titik akhir, ambil jalur di sepanjang pusatnya (ketika dua lingkaran berpotongan, segmen antara pusat mereka selalu berada dalam persatuan mereka) .) Meskipun pendekatan ini secara teknis benar, itu dapat menyebabkan sejumlah besar jalur. Sementara saya bisa menyelesaikan kasus uji pertama menggunakan pendekatan ini dalam beberapa detik, yang kedua membutuhkan waktu lama. Namun, kita dapat menggunakan metode ini sebagai titik awal dan mencoba meminimalkan jumlah jalur yang harus kita uji. Inilah yang berikut.

Kami membuat jalur kami dengan melakukan pencarian kedalaman-pertama pada grafik lingkaran. Kami sedang mencari cara untuk menghilangkan arah pencarian potensial di setiap langkah pencarian.

Misalkan pada titik tertentu kita berada pada lingkaran A , yang memiliki dua lingkaran yang berdekatan B dan C , yang juga berdekatan satu sama lain. Kita dapat pergi dari A ke C dengan mengunjungi B (dan sebaliknya,) sehingga kita mungkin berpikir bahwa mengunjungi B dan C langsung dari A tidak perlu. Sayangnya, ini salah, karena ilustrasi ini menunjukkan:

Jika titik-titik dalam ilustrasi adalah dua titik akhir, kita dapat melihat bahwa dengan pergi dari A ke C hingga B kita mendapatkan jalan yang lebih panjang.

Bagaimana dengan yang ini: jika kita menguji kedua gerakan A → B dan A → C , maka tidak perlu untuk menguji A → B → C atau A → C → B → , karena mereka tidak dapat menghasilkan jalur yang lebih pendek. Salah lagi:

Intinya adalah bahwa menggunakan argumen berbasis adjacency murni tidak akan memotongnya; kita harus menggunakan geometri masalah juga. Kesamaan dari kedua contoh di atas (dan juga test-case kedua pada skala yang lebih besar), adalah bahwa ada "lubang" di area tertutup. Ini memanifestasikan dirinya dalam kenyataan bahwa beberapa titik-titik-persimpangan pada batas — "paku" kita - berada di dalam segitiga △ ABC yang simpulnya adalah pusat lingkaran:

Ketika ini terjadi, ada kemungkinan bahwa beralih dari A ke B dan dari A ke C akan menghasilkan jalur yang berbeda. Lebih penting lagi, ketika itu tidak terjadi (yaitu jika tidak ada kesenjangan antara A , B dan C ) maka dijamin bahwa semua jalur dimulai dengan A → B → C dan dengan A → C dan yang sebaliknya setara akan menghasilkan di jalur minimal lokal yang sama, maka jika kita mengunjungi B kita tidak perlu juga mengunjungi C langsung dari A .

Ini mengarahkan kita ke metode eliminasi kita: Ketika kita berada di lingkaran A , kita menyimpan daftar H dari lingkaran yang berdekatan yang telah kita kunjungi. Daftar ini awalnya kosong. Kami mengunjungi lingkaran B yang berdekatan jika ada "paku" di semua segitiga yang dibentuk oleh pusat A , B dan salah satu lingkaran di H yang berdekatan dengan B . Metode ini secara dramatis menurunkan jumlah jalur yang harus kita uji menjadi hanya 1 pada test-case pertama dan 10 pada yang kedua.

Beberapa catatan lagi:

• Dimungkinkan untuk mengurangi jumlah jalur yang kami uji lebih jauh, tetapi metode ini cukup baik untuk skala masalah ini.

• Saya menggunakan algoritma dari solusi saya untuk tantangan karet-band. Karena algoritme ini bersifat inkremental, maka dapat dengan mudah diintegrasikan ke dalam proses pencarian jalur, sehingga kami meminimalkan jalur saat berjalan. Karena banyak jalur berbagi segmen awal, ini dapat secara signifikan meningkatkan kinerja ketika kami memiliki banyak jalur. Ini juga dapat merusak kinerja jika ada lebih banyak jalan buntu daripada jalur yang valid. Either way, untuk test-case yang diberikan melakukan algoritma untuk setiap jalur secara terpisah cukup baik.

• Ada satu kasus tepi di mana solusi ini mungkin gagal: Jika salah satu titik pada batas adalah titik persimpangan dua lingkaran singgung maka dalam beberapa kondisi hasilnya bisa salah. Ini karena cara kerja algoritma karet-band. Dengan beberapa modifikasi itu mungkin untuk menangani kasus-kasus ini juga, tapi, sudah cukup lama.

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

Input diberikan melalui variabel Isebagai satu set tupel di ((x, y), r)mana (x, y)pusat lingkaran dan rjari-jarinya. Nilai harus floats, bukan ints. Hasilnya dicetak ke STDOUT.

Contoh

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