Mari kita plot fungsi f (x) = sin (πx) + 0,5 sin (3πx) di atas domain [-3,3] . Kita bisa menafsirkan ini sebagai tali yang longgar tergeletak di papan tulis. Sekarang mari kita pindahkan n paku ke papan pada posisi (x ₁ , y ₁ ) ke (x _n , y _n ) , di mana x _i ∈ (-3,3) dan y _i ∈ [-1,1] . Bayangkan ada dua lubang tali di ujung tali, yaitu di posisi (-3,0) dan (3,0). Kita sekarang dapat mengambil ujung tali dan menarik melalui lubang tali sampai tali itu kencang. Ini akan merusak grafik kita menjadi fungsi linear piecewise.

Beberapa gambar mungkin bisa membantu. Ambil 8 paku di (-2.8, -0.7), (-2.5, -0.9), (-1.2, .2), (-0.5, .8), (0.5, .4), (1.2, -0.9), (1,5, -0,6), (1,8, -0,8) . Tiga plot berikut menunjukkan proses yang dijelaskan di atas:

^{Untuk versi yang lebih besar: Klik kanan -> Buka di tab baru}

Dan ini adalah animasi pengetatan tali jika Anda mengalami kesulitan memvisualisasikannya:

Tantangan

Diberikan daftar "paku" (yang belum tentu diurutkan), plot kuku-kuku itu dan tali kencang jika dimulai dari bentuk fungsi di atas f .

Anda dapat menulis sebuah program atau fungsi dan mengambil input melalui STDIN, ARGV atau argumen fungsi. Anda dapat menampilkan hasilnya di layar atau menyimpan gambar ke file.

Jika hasilnya dirasterisasi, ia harus memiliki lebar minimal 300 piksel dan tinggi 100 piksel. Rentang koordinat dari (-3, -1.1) hingga (3,1.1) harus mencakup setidaknya 75% dari batas horisontal dan vertikal gambar. Skala panjang x dan y tidak harus sama. Anda harus menunjukkan paku (menggunakan setidaknya 3x3 piksel) dan string (setidaknya 1 piksel lebar). Anda mungkin atau mungkin tidak termasuk sumbu.

Warna adalah pilihan Anda, tetapi Anda membutuhkan setidaknya dua warna yang dapat dibedakan: satu untuk latar belakang dan satu untuk kuku dan tali (meskipun mungkin memiliki warna yang berbeda).

Anda dapat mengasumsikan bahwa semua paku setidaknya 10 ^-5 unit jauhnya dari f (sehingga Anda tidak perlu khawatir tentang ketidaktepatan titik mengambang).

Ini adalah kode golf, jadi jawaban tersingkat (dalam byte) menang.

Lebih banyak contoh

Berikut adalah dua contoh (lebih sederhana):

{{-2.5, 1}, {-1.5, -1}, {-0.5, 1}, {0.5, -1}, {1.5, 1}, {2.5, -1}}

(String bertepatan dengan x -aksi.)

{{-2.7, -0.5}, {-2.3, -0.5}, {-1.7, 0.5}, {-1.3, 0.5}, {-0.7, -0.5}, {-0.3, -0.5}, {0.5, 1}, {1.5, -1}, {2.5, 1}}

Ingin Tantangan lain?

Inilah Bagian II!

Python + Pycairo, 727 708 608, + PyLab, 383

from pylab import*
def f(N):
 def P(u,w,N):
    T=lambda v,p:(C(v-u,p-u)>0)==(C(w-v,p-v)>0)==(C(u-w,p-w)>0);M=[(i,n)for i,n in enumerate(N)if T(V([n[0],sin(pi*n[0])+sin(3*pi*n[0])/2]),n)]
    if M:i,n=max(M,key=lambda n:C(n[1]-u,w-u)**2);M=P(u,n,N[:i])+[n]+P(n,w,N[i+1:])
    return M
 V=array;C=cross;a=V([3,0]);plot(*zip(*([-a]+P(-a,a,map(V,sorted(N)))+[a])));N and scatter(*zip(*N));show()

Contoh

f([(-2.8,-0.7),(-2.5,-0.9),(-1.2,0.2),(-0.5,0.8),(0.5,0.4),(1.2,-0.9),(1.5, -0.6),(1.8, -0.8)])

Bagaimana itu bekerja

Misalkan kita tahu bahwa string kencang melewati dua titik A dan B (kita selalu dapat mulai dengan
A = (-3, 0) dan B = (3, 0) .) Ketika kita menarik string, itu "ingin" untuk mengambil jalur terpendek yang mungkin antara A dan B , yaitu, idealnya, segmen AB . Namun, jika ada paku di area yang dibatasi oleh fungsi ( sin πx + ... ) dan AB , maka setidaknya salah satu dari mereka harus memblokir string. Secara khusus, kuku yang terjauh dari AB dalam area tersebut harus memblokir tali. Oleh karena itu, jika C adalah paku ini, kita tahu bahwa tali kencang harus melewatiC , selain A dan B . Kita sekarang dapat mengulangi proses untuk segmen AC dan CB , dan melanjutkan dengan cara ini sampai akhirnya tidak ada lagi kuku yang mengintervensi.

Ini adalah algoritme pembagian-dan-taklukkan biner dengan pemindaian linier di setiap langkah, sehingga memiliki kompleksitas kasus terbaik O (n log n) dan kompleksitas kasus terburuk O (n ² ) .

Python + pylab, 576 byte

Algoritma:

Saya menafsirkan masalah sebagai menemukan jalur terpendek dari (-3, 0) ke (3, 0) sehingga segmen garis vertikal yang menghubungkan titik di jalur ke titik di f (x) tidak pernah melintasi paku.

Pada setiap x di mana ada setidaknya satu paku, temukan batas atas dan batas bawah terbesar yang diberikan oleh paku pada x tersebut . Pertimbangkan titik yang diberikan oleh batas ini ditambah titik awal dan akhir sebagai simpul pada grafik. Tambahkan tepi dengan bobot yang diberikan oleh jarak Euclidean antara dua simpul jika segmen garis di antara mereka berada dalam batas atas dan bawah untuk setiap koordinat x yang saling berhubungan. Temukan jalur terpendek pada grafik ini.

Contoh dengan 27 poin acak:

(-0.367534, -0.722751), (-0.710649, -0.701412), (1.593101, -0.484983), (1.771199, 0.681435), (-1.878764, -0.491436), (-0.061414, 0.628570), (-0.326483, -0.512950), (0.877878, 0.858527), (1.256189, -0.300032), (1.528120, -0.606809), (-1.343850, -0.497832), (1.078216, 0.232089), (0.930588, -0.053422), (-2.024330, -0.296681), (-2.286014, 0.661657), (-0.009816, 0.170528), (2.758464, 0.099447), (-0.957686, 0.834387), (0.511607, -0.428322), (-1.657128, 0.514400), (1.507602, 0.507458), (-1.469429, -0.239108), (0.035742, 0.135643), (1.194460, -0.848291), (2.345420, -0.892100), (2.755749, 0.061595), (0.283293, 0.558334), 

Golf

Apa yang muncul sebagai beberapa spasi lekukan dalam for j in R(i&~1)loop seharusnya menjadi tab.

from pylab import*
P=((3,0),(-3,0))+input()
X=sorted(set(zip(*P)[0]))
l=len(X)*2
if l>4:scatter(*zip(*P[2:]))
f=lambda x:sin(pi*x)+sin(3*pi*x)/2
B=[[max([-9]+[p[1]for p in P if x==p[0]and p[1]<f(x)]),min([9]+[p[1]for p in P if x==p[0]and p[1]>f(x)])]for x in X]
b=zeros(l);b[2:]=inf
v=list(b)
R=range
for i in R(l):
 for j in R(i&~1):
    A=B[j/2][j&1];D,d=B[i/2][i&1]-A,X[i/2]-X[j/2];K=1;c=b[j]+norm((d,D))
    for k in R(j/2+1,i/2):C=A+D/d*(X[k]-X[j/2]);K&=C<B[k][1];K&=C>B[k][0]
    if(c<b[i])&K:b[i]=c;v[i]=j,(X[j/2],A)
l-=2
s=P[:1]
while l/2:l,p=v[l];s+=(p,)
plot(*zip(*s))
show()

Tidak disatukan

from pylab import*
P = input()
Xn,Yn = zip(*P)
X = set(Xn+(3,-3))
f = lambda x:sin(pi*x)+sin(3*pi*x)/2
ylb = {x: max([-9]+[p[1] for p in P if p[0] == x and p[1] < f(x)]) for x in X}
yub = {x: min([9]+[p[1] for p in P if p[0] == x and p[1] > f(x)]) for x in X}
ylb[-3] = yub[3] = ylb[3] = 0
X = sorted(X)
l = len(X)
best = zeros((l,2))
best[1:] = inf
prev = [ [0,0] for i in range(l) ]
for i in range(l): # calculate min path to X[i] lb or ub
  for ib in 0,1:
    for j in range(i): # point to come from
      for jb in 0,1:
          Y2, Y1 = (ylb, yub)[ib][X[i]], (ylb, yub)[jb][X[j]]
          dy,dx = Y2 - Y1, X[i] - X[j]
          if all([Y1 + dy/dx*(x - X[j]) < yub[x] and Y1 + dy/dx*(x - X[j]) > ylb[x] for x in X[j+1:i]]):
             c = best[j][jb] + (dy**2+dx**2)**.5
             if c < best[i][ib]:
                 best[i][ib] = c
                 prev[i][ib] = j, jb, (X[j], Y1)
j, jb = l-1,0
pts = [(3,0)]
while j:
    j, jb, p = prev[j][jb]
    pts += [p]
plot(*zip(*pts))
scatter(Xn,Yn)
show()