Krótkie wyjaśnienie problemu

Napisz program, aby znaleźć minimalną odległość między dwoma punktami podróżującymi tylko na promieniach pochodzących od początku i okręgami wyśrodkowanymi na początku.

Wyjaśnienie lokalu

Teraz wyobraźmy sobie, że jesteśmy w samolocie, a na tym samolocie możemy podróżować tylko w specjalny sposób. Możemy podróżować na dowolnym promieniu pochodzącym z miejsca pochodzenia.

Możemy również podróżować po dowolnym kole na środku koła

Teraz naszym celem jest podróżowanie z jednego punktu na tym samolocie do drugiego. Jednak nie możemy po prostu podróżować prostą ścieżką euklidesową, możemy to zrobić tylko wtedy, gdy punkty spadną na promień emanujący z centrum.

Możemy podróżować na tym, ponieważ pada na jedno z naszych promieni.

Możemy również podróżować po okręgach wyśrodkowanych na początku.

Przykłady

Oto wyzwanie:

Musimy dotrzeć z jednego punktu do drugiego najkrótszą ścieżką; często jest to kombinacja podróżowania na kółkach i promieniach.

Może to jednak podróżować na dwóch promieniach.

Czasami istnieją dwie ścieżki, które pokonują minimalną odległość.

Problem

Twoim wyzwaniem jest napisanie programu, który po otrzymaniu dwóch punktów da nam minimalną odległość między nimi, jeśli będziemy przestrzegać tych zasad. Dane wejściowe mogą być podawane w postaci prostokątnej lub biegunowej, a wynik powinien wynosić jedną liczbę, odległość między nimi.

Przypadki testowe

(z prostokątnym wejściem)

(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

Haskell, 49 48 bajtów

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

Stosowanie:

> 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

Dzięki @Zgarb za uratowanie bajtu

JavaScript (ES6), 65 bajtów

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

Przyjmuje współrzędne biegunowe. Wykorzystuje sztuczkę @Angsa do zmniejszenia kąta od 0 do π. W przypadku współrzędnych prostokątnych działa coś takiego:

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

MATL , 22 bajty

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

Dane wejściowe to tablica dwóch liczb zespolonych.

Wypróbuj online! Lub sprawdź wszystkie przypadki testowe .

Wyjaśnienie

|       % 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

Rubinowy, 64 bajty

Po pierwsze, moje poddanie. Funkcja lambda z argumentami 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}

Teraz są dwa różne rozwiązania o wielkości 66 bajtów (z wyłączeniem przypisania f=), a następnie moje faktyczne przesłanie ponownie po 64 bajtach.

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}

Zgłoszenie opiera się na rozwiązaniu 2, ale używa identyczności (s-r).abs=, s+r-[s,r].min*2aby skrócić kod o 2 bajty, stąd -2wewnątrz nawiasów.

Inną godną uwagi cechą jest wyrażenie ?i.to_c.arg*4= 2 * PI bez użycia include Math. Jeśli dopuszczalna jest niższa precyzja, można ją zastąpić literałem.

Rozwiązanie 2 skomentowane w programie testowym

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

Wydajność

2.221441469079183
1.4142135623730951
1.9999342590038496
1.1996117257705434
3.1660966740274357

Mathematica 66 bajtów

Wymaga to prostokątnych współrzędnych i może wygenerować dokładne symboliczne rozwiązanie

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

Stosowanie:

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

daje:

Wydajność N @%:

{2.221441469, 1.414213562, 1.999934259, 1.199611726, 3.166096674}

Python 2, 164 126 125 132 bajtów:

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)

Jednak obecnie zastanawiam się nad tym. Akceptuje współrzędne biegunowe. Powinny być wywoływane w formacie A(r1,θ1,r2,θ2). Wysyła wartość zmiennoprzecinkową z dokładnością do 12znaczących liczb.

Wypróbuj online! (Ideone)

Prosta, prosta implementacja, która oblicza i wysyła do STDOUT minimalną wartość z tablicy co najwyżej 3 wartości zawierających:

1. minimalna wartość z sumy dwóch długości ( r1+r2) lub długości łuku łączącego dwa punkty iff r1==r2 ;
2. różnica między tymi dwoma odległościach ( abs(r1-r2)) wtedy i tylko wtedy θ1==θ2 (czyli dwa punkty są współliniowe);
3. jeśli żaden z poprzednich 2 elementów nie zostanie dodany, wówczas pusty ciąg ( ''), jak widać w Pythonie, ciąg jest większy niż jakakolwiek liczba całkowita;
4. oraz 2 wartości końcowe podane z odległości przebytych przez okrąg i promień i odwrotnie między dwoma punktami.

Wolfram Language (Mathematica) , 47 bajtów

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

Wypróbuj online!

(bije obecną 66-bajtową odpowiedź)

Weź dane jako 2 liczby zespolone.

Mogą występować pewne problemy, jeśli dane wejściowe są symboliczne. (np. Cos@2 + I Sin@2)