Имеется деревянный куб со стороной 1 м. Жук может ползти по поверхности деревянного куба со скоростью 10 мм/с, и он может прогрызать его в любом направлении со скоростью 1 мм/с.
Написать программу, которая по начальным и конечным координатам жука (они могут быть как внутри куба, так и на поверхности) определит минимальное время, необходимое для преодоления этой дистанции.

Здравствуйте, nikov, Вы писали:

N>Имеется деревянный куб со стороной 1 м. Жук может ползти по поверхности деревянного куба со скоростью 10 мм/с, и он может прогрызать его в любом направлении со скоростью 1 мм/с.

Ползать можно с любой стороны, в т.ч. снизу.

Здравствуйте, nikov, Вы писали:

N>Имеется деревянный куб со стороной 1 м. Жук может ползти по поверхности деревянного куба со скоростью 10 мм/с, и он может прогрызать его в любом направлении со скоростью 1 мм/с.
N>Написать программу, которая по начальным и конечным координатам жука (они могут быть как внутри куба, так и на поверхности) определит минимальное время, необходимое для преодоления этой дистанции.

1. Построить из обеих точек перпендикуляры на грани. Выбрать самые короткие из 6 возможных (если точка равноудалена от ближайших граней, таких перпендикуляров будет 2, 3 на кубовой диагонали или 6 в центре).

2. Для каждого короткого перепендикуляра из обеих точек найти его пересечение с ближайшей гранью и занести все пересечения в два массива: A1 (из начальной) и A2 (из конечной).

3. Перебрать попарные комбинации точек из A1 и A2, для каждой пары вычислить расстояние по поверхности:

3а. Если грань общая (совпадают иксы, игреки или зеты), то это корень квадратный из суммы квадратов дельт несовпадающих координат.
3б. Если грани смежные, то строятся перпендикуляры из каждой точки до ребра смежности и находится точка на середине этого отрезка. По каждой из граней вычисляется расстояние до этой точки как указано в 3а.
3в. Если грани противоположные, <...> [тут моя мысль остановилась, потом додумаю]

Вычисленные расстояния заносятся в массив вещественных чисел A3.

Вычисляется расстояние по прямой P.

Далее return min(A3.GetMin() / 10, P).

Здравствуйте, Аноним, Вы писали:

А>[skipped]

Почти всё неправильно.

Здравствуйте, Аноним, Вы писали:

А>1. Построить из обеих точек перпендикуляры на грани. Выбрать самые короткие из 6 возможных (если точка равноудалена от ближайших граней, таких перпендикуляров будет 2, 3 на кубовой диагонали или 6 в центре).

Нафига на поверхность-то всегда выползать?

Здравствуйте, samius, Вы писали:

S>Нафига на поверхность-то всегда выползать?

А он в конце сравнивает с временем по прямой.

Здравствуйте, nikov, Вы писали:

N>Почти всё неправильно.

А можно привести пример, когда не сработает?

Здравствуйте, nikov, Вы писали:

N>Почти всё неправильно.

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

Здравствуйте, nikov, Вы писали:

N>Имеется деревянный куб со стороной 1 м. Жук может ползти по поверхности деревянного куба со скоростью 10 мм/с, и он может прогрызать его в любом направлении со скоростью 1 мм/с.
N>Написать программу, которая по начальным и конечным координатам жука (они могут быть как внутри куба, так и на поверхности) определит минимальное время, необходимое для преодоления этой дистанции.

Имеется полый фанерный куб. Скорость звука в воздухе внутри куба — 1 уе, в фанере — 10 уе.
Определить время прохождения звука между двумя заданными точками.

Сделаем щелчок в точке-излучателе.
Звуковая волна сначала принимает форму сферы и распространяется со скоростью 1 уе, пока не коснётся стенки.
После чего по стенке запускается круговая волна со скоростью 10 уе — сверхзвуковая. Она переизлучается обратно в пространство в форме конуса, тангенс угла между образующей и осью — 10/1.
К нашему счастью, этот конус не успевает достигнуть противоположной стенки по воздуху, — по поверхности фронт добегает быстрее. Иначе пришлось бы нам ещё и переизлучения рассматривать...
Правда, когда поверхностная волна переползает на другую грань, она даёт жизнь новому конусу.

В общем, надо рассмотреть суперпозицию из 1 сферы и 6*6 конусов.


Рассмотрим порождение конуса более внимательно.
Пусть излучатель находится на расстоянии d от стенки. Но ведь нам всё равно, внутри или снаружи он находится! Касание сферы произойдёт через d/v, и дальше зародится этот самый конус.
Можно сразу представить, что с внешней стороны куба движется коническая ударная волна, касающаяся через d/v стенки и продолжающая двигаться дальше.

Следовательно, можно ввести виртуальный излучатель конической волны, с вершиной — точкой, зеркально отражённой от стенки.
Физически, этот излучатель сам имеет форму конуса.

С конусами, перебежавшими на соседние грани — аналогично (только я сейчас не очень хочу думать, как именно). Какие-то отражения...

Короче говоря.
Очень просто находим расположение 37 излучателей — и затем находим расстояние от каждого из них до точки приёмника.
Расстояние от точки до конуса — элементарно. Рассматриваем плоскость, образованную осью конуса и точкой. Задача сводится к расстоянию между точкой и углом из двух лучей.

Здравствуйте, Аноним, Вы писали:

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

То есть разогнуть по соединяющему эти две грани ребру? Опять неправильно.

Здравствуйте, nikov, Вы писали:

N>Здравствуйте, Аноним, Вы писали:

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

N>То есть разогнуть по соединяющему эти две грани ребру? Опять неправильно.

Неправильно что? Определение расстояния строго по поверхности между двумя точками на смежных гранях?

Здравствуйте, Аноним, Вы писали:

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

N>>То есть разогнуть по соединяющему эти две грани ребру? Опять неправильно.

А>Неправильно что? Определение расстояния строго по поверхности между двумя точками на смежных гранях?

Да.

Здравствуйте, nikov, Вы писали:

N>Имеется деревянный куб со стороной 1 м. Жук может ползти по поверхности деревянного куба со скоростью 10 мм/с, и он может прогрызать его в любом направлении со скоростью 1 мм/с.
N>Написать программу, которая по начальным и конечным координатам жука (они могут быть как внутри куба, так и на поверхности) определит минимальное время, необходимое для преодоления этой дистанции.

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

2) зная направления движения по поверхности куба, нужно срезать углы выхода на поверхность (выход по перепендикулярам не оптимальный)

3) Выбрать минимальный путь с учетом прямого пути внутри куба. (да, не дочитал до этого момента у Анонима)


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

Иллюстрация:

Здравствуйте, Кодт, Вы писали:

К>Иллюстрация:
К>[img]http://files.rsdn.ru/4783/sound.gif[/img]

Ух ты, где рисовал?

Здравствуйте, nikov, Вы писали:

N>Ух ты, где рисовал?

Xara eXtreme.
По-хорошему, надо было какой-нибудь редактор флеша. А то заманался вручную каждую линию двигать, да ещё подгонять под физическую модель.

Здравствуйте, Кодт, Вы писали:

К>Следовательно, можно ввести виртуальный излучатель конической волны, с вершиной — точкой, зеркально отражённой от стенки.
К>Физически, этот излучатель сам имеет форму конуса.

К>С конусами, перебежавшими на соседние грани — аналогично (только я сейчас не очень хочу думать, как именно). Какие-то отражения...

Не отражения, а повороты на 90°.

Здравствуйте, nikov, Вы писали:

N>Имеется деревянный куб со стороной 1 м. Жук может ползти по поверхности деревянного куба со скоростью 10 мм/с, и он может прогрызать его в любом направлении со скоростью 1 мм/с.
N>Написать программу, которая по начальным и конечным координатам жука (они могут быть как внутри куба, так и на поверхности) определит минимальное время, необходимое для преодоления этой дистанции.

В общем случае решение такое: либо напрямую из начальной точки в конечную, либо под углом к грани с тангенсом sqrt(99) летим к одной грани, далее по прямой на одной из разверток куба бежим по граням куба, добегаем до точки, откуда по прямой с таким же тангенсом летим в конечную точку.

Сначала список утверждений для решения. А потом решение в общем виде в конце.

1) Рассмотрим одну "грань" куба -- бесконечную плоскость. Пусть две точки "висят" на высоте x и y над плоскостью. А расстояние между основаниями опущенных из них на плоскость перпендикуляров равно z. Т.е. "сбоку" вид такой:

*
|
|x       *
|        |y
----------
    z

Движение в воздухе со скоростью 1/10. А на плоскости -- 1. Каков оптимальный маршрут из одной точки в другую? Мы можем по прямой спуститься из левой точки на отрезок z на расстояние a от левого перпендикуляра, затем пройти по плоскости, пока расстояние до правого перпендикуляра не будет b, а затем по прямой полететь во вторую точку. Либо, просто напрямую лететь во вторую точку.

В первом случае время равно 10sqrt(x^2+a^2)+10sqrt(y^2+b^2)+(z-a-b). Дифференцируем по a. 99a^2=x^2. Получаем, что оптимальнее всего лететь в точку на расстоянии a=x/sqrt(99), что чуть больше 0.1x. Далее, мы двигаемся по плоскости, пока не дойдем до второго перпендикуляра на расстояние y/sqrt(99), а оттуда взлетаем ко второй точке. Здесь есть одно "но": а что, если z меньше, чем (x+y)/sqrt(99). В этом случае, как легко понять, и мы это увидим, надо лететь напрямую. Время, которое нам на это надо, равно 100(x+y)/sqrt(99)+z-(x+y)/sqrt(99)=(x+y)sqrt(99)+z.

Во втором случае (летим напрямую), время 10sqrt(z^2+(x-y)^2).

Напрямую (не через плоскость) добираться имеет смысл, если (x+y)sqrt(99)+z > 10sqrt(z^2+(x-y)^2)
или 99(x+y)^2+z^2+2sqrt(99)(x+y)z > 100(x-y)^2+100z^2
или 400xy > x^2+y^2+99z^2-2sqrt(99)(x+y)z+2xy = (x + y — sqrt(99)z)^2.

Пусть (x+y)/sqrt(99)>z. Тогда двигаться напрямую -- быстрее, чем лететь в любую точку на отрезке z, а оттуда сразу стартовать в другую точку (очевидно, т.к. все время движемся со скоростью 1/10, но по треугольнику, а не напрямую). С другой стороны, т.к. оптимальнее всего лететь как можно ближе к точке на расстоянии x/sqrt(99), а взлетать из точки на расстоянии y/sqrt(99), и (x+y)/sqrt(99)>z, то любое решение, при котором мы летим на отрезок, затем двигаемся по нему, а затем взлетаем, также будет неоптимальным). Короче, если (x+y)/sqrt(99)>z, то летим напрямую. А сравнение выше рассматриваем только для (x+y)<sqrt(99)z, т.е., когда мы возьмем корень от обеих частей, то справа будет не x+y-sqrt(99)z (отрицательное), а sqrt(99)z-(x+y).

Итак, летим напрямую, если sqrt(99)z < x + y + 20sqrt(xy) (***)
Во как!

2) Рассмотрим теперь движение из одной точки на грани в другую точку на другой грани. Как вариант, можно предположить, что, пересекая общее ребро, мы захотим срезать и пролетим часть внутри куба. Как легко видеть, это не так. В этом случае мы вместо того, чтобы двигаться по стороне куба до ребра, а оттуда до другой точки другой грани (две стороны некоторого треугольника), захотим срезать внутри куба (т.е. полетим по третьей стороне этого треугольника, которая проходит внутри куба). Но эта третья сторона не может быть в 10 раз меньше, чем сумма двух других сторон. Даже если предположить, что мы сначала двигаемся перпендикулярно ребру, что далеко не всегда оптимально, а потом в конечную точку, то для такого прямоугольного треуголька гипотенуза может быть только в sqrt(2) раз меньше суммы катетов. А для оптимального треугольника -- и того меньше. Короче, при переходе с грань на грань мы углы не срезаем. При движении с одной грани на противоположную -- тем более. Пока мы внутри куба летим в 10 раз медленнее, чем по граням, за это время весь куб по периметру можно 2 раза обойти.

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

так: ---  или так:  ---   ---
    |  *|          |  *| |   |
    |   |          |   | |   |
     ---            ---   ---
    |   |                |  *|
    |  *|                |   |
     ---                  ---

Как быстрее, так и двигаемся.

Собственно, решение такое:
а) Рассматриваем 6 перпендикуляров (проекций) на грани для исходной точки и для конечной точки.
б) Для различных комбинаций начальной и конечной проекции находим расстояние по граням куба (кратчайшая прямая по одной из разверток куба).
в) Рассматривая соответствующую развертку, получаем задачу из пункта 1). Т.е. оптимальное движение будет таким, что мы летим под углом с тангенсом sqrt(99) к грани, далее бежим по той самой прямой до того места, откуда снова под этим же углом попадаем в нужную точку. Кстати, для проверки проекций (исходной и конечной) на одной грани можно сразу воспользоваться формулой (***).
г) Сравниваем результаты пункта в) с прямым полетом из начальной точки в конечную.

Здравствуйте, vadimcher, Вы писали:

V>В общем случае решение такое: либо напрямую из начальной точки в конечную, либо под углом к грани с тангенсом sqrt(99) летим к одной грани, далее по прямой на одной из разверток куба бежим по граням куба, добегаем до точки, откуда по прямой с таким же тангенсом летим в конечную точку.

Кажется, твоё решение изоморфно моему.
Только с той разницей, что тебе надо рассмотреть все развёртки, а мне — все конические источники.

А для плоского случая эта задача была сформулирована то ли Маковецким в "Зри в корень", то ли даже Перельманом в "Занимательной" серии.

Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, vadimcher, Вы писали:

V>>В общем случае решение такое: либо напрямую из начальной точки в конечную, либо под углом к грани с тангенсом sqrt(99) летим к одной грани, далее по прямой на одной из разверток куба бежим по граням куба, добегаем до точки, откуда по прямой с таким же тангенсом летим в конечную точку.

К>Кажется, твоё решение изоморфно моему.

Очень может быть, я пока в твое не въехал. Сейчас перечитаю.

К>Только с той разницей, что тебе надо рассмотреть все развёртки, а мне — все конические источники.
К>А для плоского случая эта задача была сформулирована то ли Маковецким в "Зри в корень", то ли даже Перельманом в "Занимательной" серии.

Наверное, правда, я не помню такой. Хотя я их так толком целиком и не прочитал, только выборочно.