Entfernung zwischen zwei Punkten, die auf einem Polardiagramm reisen

23

Kurze Erklärung des Problems

Schreiben Sie ein Programm, um den Mindestabstand zwischen zwei Punkten zu ermitteln, die sich nur auf Strahlen aus dem Ursprung und auf Kreisen ausrichten, die auf dem Ursprung zentriert sind.

Erklärung der Prämisse

Stellen wir uns nun vor, wir sind in einem Flugzeug, und in diesem Flugzeug dürfen wir nur auf besondere Weise reisen. Wir dürfen mit jedem Strahl reisen, der vom Ursprung ausgeht.

Strahlen, auf denen wir reisen können

Wir können auch auf jedem Kreis fahren, der in der Mitte eines Kreises liegt

Kreise, auf denen wir reisen können

Jetzt ist es unser Ziel, von einem Punkt in diesem Flugzeug zum anderen zu reisen. Wir können jedoch nicht einfach auf einem einfachen euklidischen Pfad wandern, sondern nur, wenn die Punkte zufällig auf einen Strahl fallen, der vom Zentrum ausgeht.

Bildbeschreibung hier eingeben

Wir können mit diesem reisen, weil es auf einen unserer Strahlen fällt.

Bildbeschreibung hier eingeben

Wir können auch auf Kreisen fahren, die am Ursprung zentriert sind.

Bildbeschreibung hier eingeben

Beispiele

Hier ist die Herausforderung:

Wir müssen auf dem kürzesten Weg von einem Punkt zum anderen gelangen. Oft ist dies eine Kombination aus Reisen auf Kreisen und Strahlen.

Bildbeschreibung hier eingeben

Dies könnte jedoch auch auf zwei Strahlen erfolgen.

Bildbeschreibung hier eingeben

Manchmal gibt es zwei Pfade, die die Mindestentfernung zurücklegen.

Bildbeschreibung hier eingeben

Problem

Ihre Herausforderung besteht darin, ein Programm zu schreiben, das bei zwei gegebenen Punkten den Mindestabstand zwischen ihnen ergibt, wenn wir diese Regeln einhalten. Die Eingaben können entweder in rechteckiger oder in polarer Form erfolgen, und die Ausgabe sollte eine Zahl sein, der Abstand zwischen ihnen.

Testfälle

(mit rechteckigem Eingang)

(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
quelle
Handelt es sich bei den Beispiel-Testfällen um rechteckige oder polare Formen? Also: bewteen
Angs
Sie sind in der rechteckigen Form, ich sollte das klarstellen
Ando Bando
Ist das letzte Beispiel richtig? Ich bekomme ~ 3.166
Angs
6
@Peter Taylor Weil sie nicht wirklich den gleichen Weg sind. In ähnlicher Weise erscheint ein Pfad von 0,0 bis 1,1 in der xy-Ebene über kleine Schritte, die sich in x- und y-Richtung abwechseln, identisch mit einem direkten diagonalen Pfad, da die Schrittlänge gegen Null tendiert. Der diagonale Pfad hat jedoch die Länge sqrt (2), während der
Stufenpfad
1
Ich denke, die Herausforderung würde besser aussehen, wenn die Bilder nicht so groß wären. Derzeit ist es schwierig, dem Text zu folgen
Luis Mendo

Antworten:

5

Haskell, 49 48 Bytes

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

Verwendung:

> 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

Vielen Dank an @Zgarb für das Speichern eines Bytes

Angs
quelle
Sie können ein Byte speichern, indem Sie (a!q)c ranstelle von definieren 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

Nimmt Polarkoordinaten. Verwendet den @Angs-Trick, um einen Winkel zwischen 0 und π zu reduzieren. Für rechteckige Koordinaten funktioniert so etwas:

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
quelle
3

MATL , 22 Bytes

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

Die Eingabe ist ein Array von zwei komplexen Zahlen.

Probieren Sie es online! Oder überprüfen Sie alle Testfälle .

Erläuterung

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

Ruby, 64 Bytes

Erstens meine Vorlage. Lambda-Funktion mit Argumenten 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}

Hier sind zwei verschiedene Lösungen mit 66 Bytes (ohne Zuweisung f=), gefolgt von meiner tatsächlichen Einreichung mit 64 Bytes.

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}

Die Einreichung basiert auf Lösung 2, verwendet jedoch identity (s-r).abs= s+r-[s,r].min*2, um den Code um 2 Bytes zu kürzen, daher das -2Wort in Klammern.

Das andere bemerkenswerte Merkmal ist der Ausdruck ?i.to_c.arg*4= 2 * PI ohne Verwendung include Math. Wenn eine geringere Genauigkeit akzeptabel ist, kann diese durch ein Literal ersetzt werden.

Lösung 2 im Testprogramm kommentiert

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

Ausgabe

2.221441469079183
1.4142135623730951
1.9999342590038496
1.1996117257705434
3.1660966740274357
Level River St
quelle
2

Mathematica 66 Bytes

Dies nimmt rechteckige Koordinaten und kann eine exakte symbolische Lösung ausgeben

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

Verwendung:

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

ergibt: symbolisches Ergebnis

N @% ergibt:

{2.221441469, 1.414213562, 1.999934259, 1.199611726, 3.166096674}

Kelly Lowder
quelle
1
Flott! Wenn Sie den symbolischen Weg gehen, können Sie den Testfall {1,0} {-. 4161, .90929} durch {1,0} {cos (2), sin (2)}
Ando Bando
1

Python 2, 164 126 125 132 Bytes:

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)

Ich beschäftige mich momentan jedoch mehr mit Golfspielen. Akzeptiert Polarkoordinaten. Sollte im Format aufgerufen werden A(r1,θ1,r2,θ2). Gibt einen Gleitkommawert mit einer Genauigkeit von bis zu 12signifikanten Zahlen aus.

Probieren Sie es online! (Ideone)

Eine einfache, unkomplizierte Implementierung, die den Mindestwert aus einem Array von höchstens 3 Werten berechnet und an STDOUT ausgibt, das Folgendes enthält:

  1. der Mindestwert entweder aus der Summe der beiden Längen ( r1+r2) oder der Länge des Bogens, der die beiden Punkte verbindet, wennf r1==r2 ;
  2. die Differenz zwischen den beiden Abständen ( abs(r1-r2)) iff θ1==θ2 (dh die beiden Punkte sind kollinear);
  3. Wenn keines der beiden vorherigen Elemente hinzugefügt wird, ist eine leere Zeichenfolge ( ''), wie anscheinend in Python, größer als eine ganze Zahl.
  4. und 2 Endwerte, die sich aus den Entfernungen ergeben, die entlang eines Kreises und eines Strahls und umgekehrt zwischen den beiden Punkten zurückgelegt wurden.
R. Kap
quelle
Warum nicht math.pi?
user202729
0

Wolfram-Sprache (Mathematica) , 47 Bytes

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

Probieren Sie es online!

(übertrifft die aktuelle 66-Byte-Antwort)

Nimm die Eingabe als 2 komplexe Zahlen.

Kann einige Probleme haben, wenn die Eingabe symbolisch ist. (zB Cos@2 + I Sin@2)

user202729
quelle