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

23

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

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

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

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

Лучи, по которым мы можем путешествовать

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

Круги, по которым мы можем путешествовать

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

введите описание изображения здесь

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

введите описание изображения здесь

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

введите описание изображения здесь

Примеры

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

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

введите описание изображения здесь

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

введите описание изображения здесь

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

введите описание изображения здесь

проблема

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

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

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

(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
Андо Бандо
источник
Примеры тестовых случаев в прямоугольной или полярной форме? Также:
bewteen
Они в прямоугольной форме, я должен уточнить, что
Андо Бандо
Верен ли последний пример? Я получаю ~ 3.166
Angs
6
@ Питер Тейлор Потому что они на самом деле не один и тот же путь. Аналогичным образом путь от 0,0 до 1,1 на плоскости xy с помощью небольших шагов, чередующихся в направлениях x и y, выглядит идентичным прямому диагональному пути, поскольку длина шага стремится к нулю. Но диагональный путь имеет длину sqrt (2), в то время как путь шага всегда будет иметь длину 2.
Penguino
1
Я думаю, что проблема выглядела бы лучше, если бы изображения были не такими большими. В настоящее время им трудно следить за текстом
Луис Мендо,

Ответы:

5

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 за сохранение байта

Angs
источник
Вы можете сохранить байт, определив (a!q)c rвместо d a q c r.
Згарб
4

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))
Нил
источник
3

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
Луис Мендо
источник
2

Рубин, 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
Уровень реки St
источник
2

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}

Келли Лоудер
источник
1
Острота! если вы идете по символическому маршруту, вы можете заменить контрольный пример {1,0} {-. 4161, .90929} на {1,0} {cos (2), sin (2)}
Ando Bando
1

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 окончательных значения даны из расстояний, пройденных по кругу и лучу, и наоборот между двумя точками.
Р. Кап
источник
Почему нет math.pi?
user202729
0

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

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

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

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

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

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

user202729
источник