Jarak Antara Dua Poin Bepergian pada Bagan Grafik Polar

23

Penjelasan Masalah Singkat

Tulis program untuk menemukan jarak minimum antara dua titik yang hanya bepergian dengan sinar yang berasal dari titik asal dan lingkaran yang berpusat di titik asal.

Penjelasan Premis

Sekarang mari kita bayangkan kita berada di pesawat, dan di pesawat ini kita hanya boleh bepergian dengan cara khusus. Kami diizinkan melakukan perjalanan dengan sinar apa pun yang berasal dari asal.

Sinar yang bisa kita bawa

Kita juga bisa bepergian di lingkaran mana saja yang berpusat pada lingkaran

Lingkaran yang bisa kita tempuh

Sekarang tujuan kami adalah melakukan perjalanan dari satu titik di pesawat ini ke yang lain. Namun, kita tidak bisa hanya melakukan perjalanan di jalur Euclidian sederhana, kita hanya bisa melakukan ini jika titik-titik jatuh pada sinar yang berasal dari pusat.

masukkan deskripsi gambar di sini

Kita dapat melakukan perjalanan ini karena itu jatuh pada salah satu dari sinar kita.

masukkan deskripsi gambar di sini

Kita juga bisa bepergian dengan lingkaran yang berpusat di titik asal.

masukkan deskripsi gambar di sini

Contohnya

Sekarang inilah tantangannya:

Kita harus berpindah dari satu titik ke titik lainnya di jalur terpendek; sering kali ini merupakan kombinasi bepergian dengan lingkaran dan sinar.

masukkan deskripsi gambar di sini

Ini, bagaimanapun, bisa juga bepergian dengan dua sinar.

masukkan deskripsi gambar di sini

Terkadang ada dua jalur yang menempuh jarak minimum.

masukkan deskripsi gambar di sini

Masalah

Tantangan Anda adalah menulis sebuah program yang ketika diberi dua poin akan memberi kami jarak minimum di antara mereka jika kami mengikuti aturan ini. Input dapat diberikan dalam bentuk persegi panjang atau kutub dan output harus satu angka, jarak antara.

Uji Kasus

(dengan input persegi panjang)

(1,1) (1,-1) -> ~ 2.22144
(0,0) (1, 1) -> ~ 1.41421
(1,0) (-0.4161 , 0.90929) -> ~ 2
(1,1) (1, 0) -> ~ 1.19961
(1,2) (3, 4) -> ~ 3.16609
Ando Bando
sumber
Apakah contoh kasus uji dalam bentuk persegi panjang atau kutub? Juga: bewteen
Angs
Mereka berada dalam bentuk persegi panjang, saya harus mengklarifikasi bahwa
Ando Bando
Apakah contoh terakhir benar? Saya mendapatkan ~
3.166
6
@ Peter Taylor Karena mereka tidak benar-benar jalan yang sama. Dengan cara yang sama jalur dari 0,0 ke 1,1 pada bidang xy melalui langkah-langkah kecil bergantian dalam arah x dan y tampak identik dengan jalur diagonal langsung karena panjang langkah cenderung ke nol. Tetapi jalur diagonal memiliki panjang sqrt (2) sedangkan jalur langkah akan selalu memiliki panjang 2.
Penguino
1
Saya pikir tantangannya akan terlihat lebih baik jika gambarnya tidak terlalu besar. Saat ini mereka membuat sulit untuk mengikuti teks
Luis Mendo

Jawaban:

5

Haskell, 49 48 byte

(a!q)c r=min(q+r)$abs(q-r)+acos(cos$a-c)*min q r

Pemakaian:

> let rect2polar (x,y)=(atan2 y x, sqrt(x^2+y^2))
> let test c1 c2=let [(a1,r1),(a2,r2)]=rect2polar<$>[c1,c2] in (a1!r1)a2 r2
> test (1,0) (-0.4161, 0.90929)
1.9999342590038496

Terima kasih kepada @Zgarb karena telah menghemat satu byte

Angs
sumber
Anda dapat menyimpan byte dengan mendefinisikan (a!q)c ralih-alih d a q c r.
Zgarb
4

JavaScript (ES6), 65 byte

with(Math)(r,t,s,u,v=acos(cos(t-u)))=>v<2?abs(r-s)+v*min(r,s):r+s

Mengambil koordinat kutub. Menggunakan trik @Angs 'untuk mengurangi sudut antara 0 dan π. Untuk koordinat persegi panjang, sesuatu seperti ini berfungsi:

with(Math)g=(r,t,s,u,v=acos(cos(t-u)))=>v<2?abs(r-s)+v*min(r,s):r+s
with(Math)f=(x,y,v,w)=>g(hypot(y,x),atan2(y,x),hypot(w,v),atan2(y,v))
Neil
sumber
3

MATL , 22 byte

|ttsGZ}/X/bX<*|bd|+hX<

Input adalah array dari dua bilangan kompleks.

Cobalah online! Atau verifikasi semua kasus uji .

Penjelasan

|       % Implicitly input array and take absolute value of its entries
tt      % Duplicate twice
s       % Sum. This is the length of the path that follows the two radii
GZ}     % Push input again and split into the two numbers
/X/     % Divide and compute angle. This gives the difference of the angles
        % of the two points, between -pi and pi
bX<     % Bubble up a copy of the array of radii and compute minimum
*|      % Multiply and take absolute value. This is the arc part of the
        % path that follows one arc and the difference of radii
bd|     % Bubble up a copy of the array of radii and compute absolute
        % difference. This is the other part of the second path
+       % Add. This gives the length of second path
hX<     % Concatenate and take minimum to produce the smallest length.
        % Implicitly display
Luis Mendo
sumber
2

Ruby, 64 byte

Pertama, pengajuan saya. Fungsi Lambda dengan argumen distance 1, angle 1, distance 2, angle2.

->r,a,s,b{([d=(b-a).abs,?i.to_c.arg*4-d,2].min-2)*[r,s].min+s+r}

Sekarang inilah dua solusi berbeda dari 66 byte (tidak termasuk penugasan f=) diikuti oleh kiriman aktual saya lagi pada 64 byte.

Solution 1:Using include Math, 66 bytes excluding f=
include Math;f=->r,a,s,b{[acos(cos(b-a)),2].min*[r,s].min+(s-r).abs}

Solution 2:Using complex number to define PI instead, 66 bytes excluding f=
f=->r,a,s,b{[d=(b-a).abs,?i.to_c.arg*4-d,2].min*[r,s].min+(s-r).abs}

SUBMISSION AGAIN, 64 bytes excluding f=
f=->r,a,s,b{([d=(b-a).abs,?i.to_c.arg*4-d,2].min-2)*[r,s].min+s+r}

Pengajuan didasarkan pada solusi 2, tetapi menggunakan identitas (s-r).abs= s+r-[s,r].min*2untuk mempersingkat kode dengan 2 byte, maka di -2dalam kurung.

Fitur penting lainnya adalah ekspresi ?i.to_c.arg*4= 2 * PI tanpa menggunakan include Math. Jika presisi yang lebih rendah dapat diterima, ini bisa diganti dengan literal.

Solusi 2 dikomentari dalam program uji

f=->r,a,s,b{          #r,s are distances, a,b are angles for points 1 and 2 respectively.                       
    [d=(b-a).abs,       #From nearer point we can take arc of length d radians perhaps crossing zero angle to the ray of the further point
    ?i.to_c.arg*4-d,    #or go the other way round which may be shorter (?i.to_c.arg*4 == 2*PI, subtract d from this.)
    2].min*             #or go through the centre if the angle exceeds 2 radians.
  [r,s].min+          #Multiply the radians by the distance of the nearer point from the origin to get the distance travelled. 
  (s-r).abs           #Now add the distance to move along the ray out to the further point.
}

#test cases per question (given as complex numbers, converted to arrays of [distance,angle]+[distance,angle] (+ concatenates.)
#the "splat" operator * converts the array to 4 separate arguments for the function.
p f[*("1+i".to_c.polar + "1-i".to_c.polar)]
p f[*("0".to_c.polar + "1+i".to_c.polar)]
p f[*("1".to_c.polar + "-0.4161+0.90929i".to_c.polar)]
p f[*("1+i".to_c.polar + "1".to_c.polar)]
p f[*("1+2i".to_c.polar + "3+4i".to_c.polar)]

Keluaran

2.221441469079183
1.4142135623730951
1.9999342590038496
1.1996117257705434
3.1660966740274357
Level River St
sumber
2

Mathematica 66 Bytes

Ini membutuhkan koordinat persegi panjang dan dapat menghasilkan solusi simbolik yang tepat

Min[If[(m=Min[{p,q}=Norm/@#])>0,m*VectorAngle@@#,0]+Abs[p-q],p+q]&

Pemakaian:

%/@{
{{1,1},{1,-1}},
{{0,0},{1,1}},
{{1,0},{-.4161,.90929}},
{{1,1},{1,0}},
{{1,2},{3,4}}
}

hasil: hasil simbolis

N @% hasil:

{2.221441469, 1.414213562, 1.999934259, 1.199611726, 3.166096674}

Kelly Lowder
sumber
1
Bagus! jika Anda menggunakan rute simbolis, Anda dapat mengganti test case {1,0} {-. 4161, .90929} dengan {1,0} {cos (2), sin (2)}
Ando Bando
1

Python 2, 164 126 125 132 byte:

def A(a,b,c,d,p=3.1415926535):z=abs(a-c);M=lambda f:2*p*f*abs(b-d)/360.0;print min((a==c)*min(a+c,M(a))+(b==d)*z or'',M(a)+z,M(c)+z)

Saya saat ini melihat ke golf ini lagi. Menerima koordinat kutub. Harus dipanggil dalam format A(r1,θ1,r2,θ2). Menghasilkan nilai floating point yang akurat hingga 12angka signifikan.

Cobalah secara Online! (Ideone)

Implementasi sederhana, langsung yang menghitung dan menghasilkan untuk STDOUT nilai minimum dari array paling banyak 3 nilai yang mengandung:

  1. nilai minimum dari jumlah kedua panjang ( r1+r2) atau panjang busur yang menghubungkan dua titik iff r1==r2 ;
  2. yang perbedaan antara dua jarak ( abs(r1-r2)) IFF θ1==θ2 (yaitu dua poin collinear);
  3. jika tidak ada dari 2 item sebelumnya yang ditambahkan, maka string kosong ( '') seperti yang tampak dalam Python string lebih besar dari integer apa pun;
  4. dan 2 nilai akhir yang diberikan dari jarak yang ditempuh sepanjang lingkaran dan sinar dan sebaliknya antara dua titik.
R. Kap
sumber
Mengapa tidak math.pi?
user202729
0

Bahasa Wolfram (Mathematica) , 47 byte

MinMax@Abs@{##}.{Min[Abs[Arg@#-Arg@#2]-1,1],1}&

Cobalah online!

(mengalahkan jawaban 66 byte saat ini)

Ambil input sebagai 2 angka kompleks.

Mungkin memiliki beberapa masalah jika inputnya simbolis. (misalnya, Cos@2 + I Sin@2)

pengguna202729
sumber