Краткое объяснение проблемы

Напишите программу, чтобы найти минимальное расстояние между двумя точками, проходящими только на лучах, исходящих от источника, и окружностях с центром в начале координат.

Объяснение Помещения

Теперь давайте представим, что мы находимся в самолете, и на этом самолете нам разрешено путешествовать только особыми способами. Нам разрешено путешествовать на любом луче, исходящем из источника.

Мы также можем путешествовать по любому кругу с центром в кругу

Теперь наша цель - путешествовать из одной точки этого самолета в другую. Однако мы не можем просто путешествовать по простому евклидову пути, мы можем сделать это только в том случае, если точки попадают на луч, исходящий из центра.

Мы можем путешествовать на этом, потому что он падает на один из наших лучей.

Мы также можем путешествовать по кругу с центром в начале координат.

Примеры

Теперь вот проблема:

Мы должны добраться из одной точки в другую по кратчайшему пути; часто это сочетание путешествий по кругу и лучам.

Это, однако, может также путешествовать на двух лучах.

Иногда существуют два пути, которые проходят минимальное расстояние.

проблема

Ваша задача - написать программу, которая при наличии двух точек даст нам минимальное расстояние между ними, если мы будем следовать этим правилам. Входные данные могут быть заданы либо в прямоугольной, либо в полярной форме, а выходной должен быть одним числом, расстояние между ними.

Тестовые случаи

(с прямоугольным входом)

(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 байтов

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

Использование:

> 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

Спасибо @Zgarb за сохранение байта

JavaScript (ES6), 65 байт

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

Принимает полярные координаты. Использует трюк @Angs для уменьшения угла между 0 и π. Для прямоугольных координат что-то вроде этого работает:

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 байта

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

Ввод представляет собой массив из двух комплексных чисел.

Попробуйте онлайн! Или проверьте все тестовые случаи .

объяснение

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

Рубин, 64 байта

Во-первых, мое представление. Лямбда-функция с аргументами 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}

Теперь вот два разных решения по 66 байтов (без присваивания f=), за которым следует моё фактическое представление снова с 64 байтами.

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}

Представление основано на решении 2, но использует идентификатор (s-r).abs= s+r-[s,r].min*2для сокращения кода на 2 байта, следовательно, -2внутри скобок.

Другой примечательной особенностью является выражение ?i.to_c.arg*4= 2 * PI без использования include Math. Если более низкая точность приемлема, это может быть заменено литералом.

Решение 2 прокомментировано в тестовой программе

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

Выход

2.221441469079183
1.4142135623730951
1.9999342590038496
1.1996117257705434
3.1660966740274357

Mathematica 66 байт

Это принимает прямоугольные координаты и может вывести точное символическое решение

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

Использование:

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

выходы:

N @% выходов:

{2.221441469, 1.414213562, 1.999934259, 1.199611726, 3.166096674}

Python 2, 164, 126, 125, 132 байта:

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)

В настоящее время я больше интересуюсь игрой в гольф. Принимает полярные координаты. Должен быть назван в формате A(r1,θ1,r2,θ2). Выводит значение с плавающей запятой с точностью до 12значащих цифр.

Попробуйте онлайн! (Ideone)

Простая, простая реализация, которая вычисляет и выводит в STDOUT минимальное значение из массива не более 3 значений, содержащего:

1. минимальное значение из суммы двух длин ( r1+r2) или длины дуги, соединяющей две точки iff r1==r2 ;
2. разница между этими двумя расстояниями ( abs(r1-r2)) тогда и только тогда θ1==θ2 (т.е. две точки лежат на одной прямой);
3. если ни один из предыдущих 2 элементов не добавлен, тогда пустая строка ( ''), как, очевидно, в Python, строка больше любого целого числа;
4. и 2 окончательных значения даны из расстояний, пройденных по кругу и лучу, и наоборот между двумя точками.

Wolfram Language (Mathematica) , 47 байтов

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

Попробуйте онлайн!

(бьет текущий 66-байтовый ответ)

Примите входные данные как 2 комплексных числа.

Могут возникнуть некоторые проблемы, если ввод является символическим. (например, Cos@2 + I Sin@2)