Odległość między dwoma punktami podróżującymi na wykresie biegunowym

23

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.

Promienie, po których możemy podróżować

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

Kręgi, po których możemy podróżować

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.

wprowadź opis zdjęcia tutaj

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

wprowadź opis zdjęcia tutaj

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

wprowadź opis zdjęcia tutaj

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.

wprowadź opis zdjęcia tutaj

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

wprowadź opis zdjęcia tutaj

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

wprowadź opis zdjęcia tutaj

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
Ando Bando
źródło
Czy przykładowe przypadki testowe mają kształt prostokątny lub biegunowy? Również: bewteen
Angs,
Są w kształcie prostokąta, powinienem to wyjaśnić
Ando Bando,
Czy ostatni przykład jest poprawny? Dostaję ~
3.166
6
@Peter Taylor Ponieważ nie są tak naprawdę tą samą ścieżką. W podobny sposób ścieżka od 0,0 do 1,1 na płaszczyźnie xy małymi krokami na przemian w kierunkach xiy wydaje się identyczna z bezpośrednią ścieżką ukośną, gdy długość kroku zmierza do zera. Ale ścieżka po przekątnej ma długość sqrt (2), podczas gdy ścieżka kroku zawsze będzie miała długość 2.
Penguino,
1
Myślę, że wyzwanie wyglądałoby lepiej, gdyby obrazy nie były tak duże. Obecnie utrudniają śledzenie tekstu
Luis Mendo

Odpowiedzi:

5

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

Angs
źródło
Możesz zapisać bajt, definiując (a!q)c rzamiast d a q c r.
Zgarb
4

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))
Neil
źródło
3

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
Luis Mendo
źródło
2

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
Level River St
źródło
2

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: wynik symboliczny

Wydajność N @%:

{2.221441469, 1.414213562, 1.999934259, 1.199611726, 3.166096674}

Kelly Lowder
źródło
1
Sprytne! jeśli idziesz drogą symboliczną, możesz zastąpić przypadek testowy {1,0} {-. 4161, .90929} przez {1,0} {cos (2), sin (2)}
Ando Bando
1

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.
R. Kap
źródło
Dlaczego nie math.pi?
user202729
0

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)

użytkownik202729
źródło