Лиса, Утка и озеро.

[grizzly]

Dmitriy40 в сообщении #1289988 писал(а):

Отсюда утка попрёт вертикально вверх, в сторону увеличения $y$.

Как только утка поплыла вверх с этой точки, лиса двинулась против часовой стрелки. Допустим, пока на полной скорости.

[Dmitriy40]

Стратегия: или добегаем до указанной точки и следом до северного полюса, или если лиса дёрнулась - бежим горизонтально в противоположную сторону. Бежим пока лиса не меняет направления. Если меняет - бежим обратно к оси $OY$. После 100500 повтора Вам надоест, или я буду бежать за утку с бесконечно малым приращением по $y$ и за каждый цикл уходить севернее и когда-нибудь $y$ станет больше $0{,}2933$ при $x=0$ - оттуда утка успевает в северный полюс.

grizzly в сообщении #1289989 писал(а):

Как только утка поплыла вверх с этой точки, лиса двинулась против часовой стрелки. Допустим, пока на полной скорости.

ОК, утка двинулась влево-вверх под углом 1° от горизонтали (почти в точку $(-1;0{,}2)$). Предупреждаю, если лиса тут же разворачивается - я вернусь обратно к оси $OY$ с ненулевым бонусом по $y$.

[grizzly]

Лиса бежит в точку (0,5; -1) и ждёт пока утка доплывёт до точки (-0,088; 0,177) или изменит направление.

[Dmitriy40]

Доплыла, дальше? Про 1° так уж и быть, забуду. Вам не кажется что в этой точке мы уже были?
Эх, а ведь мог бы и до $(-1;0{,}194)$ доплыть, какая жаль ...

[grizzly]

Dmitriy40
Я плохо сыграл. Всё пошло не так, ещё с самого начала, когда Вы меня "подловили" на обещании бежать всё время в одну сторону. Я не должен был возвращаться до самой оси. Раз Вы возвращаетесь почти точно к оси, мне достаточно стоять на месте.

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

[Dmitriy40]

Дело в том что на достаточно грубой сетке решения может и не быть. 3 цифры после запятой для координат мало, возьмите точность координат хотя бы 6-7 цифр, а шаги утки и лисы 0,001/0,00566 (точно). И примените стратегию утки из обычного начального положения (утка в $(0;1/k)$, лиса в $(0;-1)$, или любого другого на пересечении диаметра и квадрата $1/k$):
1) если успеваем по горизонтальной/вертикальной прямой до любой из 4-х сторон берега быстрее кратчайшего пути лисы туда же - утка выиграла;
2) иначе двигаться влево или вправо в сторону диаметра (т.е. приводя угол из центра между уткой и лисой к 180°) под углом вверх 0,06° к горизонтали (или с увеличением $y$ на 0,000001 каждый шаг);
3) если такой шаг приводит к пересечению диаметра - сделать вместо него полный шаг вверх (защита от долгих колебаний утки около диаметра, хотя с ненулевым углом можно и исключить, но тогда иногда будет длиннюющая лесенка).
Собственно всё!
Ненулевой угол защищает от повторов туда-обратно смещая утку чуть выше, если обязуетесь не зацикливаться - можно шагать и строго по горизонтали.
Берите и считайте, всего-то одно №2 несложное правило за утку. Быстро увидите что лисе всегда выгоднее уменьшать угол между ней и уткой - а это гарантирует от разворотов.

[grizzly]

Dmitriy40
Глупостей я вчера на ночь наговорил -- не работает моя идея. Не знаю, можно ли как-то по-другому улучшить, но мою уверенность Вы здорово поколебали :) Сорри за упорствование в ошибках.

[Dmitriy40]

grizzly
Написал программулину для симуляции утки, Вы управляете лисой. Алгоритм движения утки не полный (она никогда не двигается вниз, только влево-вправо-вверх), но для тестов k=5,66 достаточный. Красоту наводить извините не стал, всё в pure text. Работает Undo и History (на 100 шагов, легко исправляется в программе в 34 строке). Количество знаков после запятой можно поменять в константе prec в 4 строке, но ставить меньше 5-6 и больше 10 смысла не вижу.
Берите, играйтесь (открыть страницу и нажать Run слева вверху если не запустилось сразу).
Текст программы можно и пересохранить в локальный html файл и запускать его в любом браузере.
Хм, типа уже не нужна? Но раз уж написал, то не выбрасывать же ...

Geen, EUgeneUS, wrest, worm2, rockclimber, возможно Вам тоже будет интересно.

[rockclimber]

Dmitriy40 в сообщении #1290064 писал(а):

rockclimber, возможно Вам тоже будет интересно.

Я не читал топик с 12-й страницы. Отошел в пятницу буквально на секундочку, возвращаюсь - было 12 страниц, стало 16. Ну и забросил. Можно резюмировать как-то, что там было?
Программу тоже хотел написать, правда, как обычно, руки не доходят. Может, чуть позже.

[grizzly]

Dmitriy40 в сообщении #1290064 писал(а):

Но раз уж написал, то не выбрасывать же ...

Спасибо! я уже попробовал. Поучительно :)

rockclimber в сообщении #1290072 писал(а):

Можно резюмировать как-то, что там было?

Да большей частью по мелочам. Спорили по поводу коэффициента для квадратного озера. Изначальная гипотеза была около 5.9, затем всего за пару страниц разобрались, что можно меньше -- 5.786 (кажется). Потом были предприняты попытки улучшить этот результат, но безуспешные. Похоже, что этот результат окончательный.

rockclimber в сообщении #1290072 писал(а):

Программу тоже хотел написать, правда, как обычно, руки не доходят. Может, чуть позже.

Делайте, пожалуйста, сразу для треугольного, если для произвольного и/или многоугольника сложно

[Dmitriy40]

rockclimber
Если кратко, то я считаю $k=(5+\sqrt{41})/2 \approx 5{,}7$ минимально возможным для лисы (при меньших у утки появляется гарантированно выигрышная стратегия). Вопрос о форме фигуры принятия решения (когда и куда лице бежать при смещении утки) остался открытым т.к. он принципиально зависит от стратегии лисы (когда она срывается, куда бежит, когда останавливается, когда разворачивается - тут много вариантов предлагалось и мало до конца проверили). Из всей фигуры понятна лишь предельная точка $(0;1-4/k)$. Ну и вроде бы с фигурой безопасности со мной уже не спорят что это таки квадрат со стороной $1/k$.

grizzly в сообщении #1290074 писал(а):

за пару страниц разобрались, что можно меньше -- 5.786 (кажется). Потом были предприняты попытки улучшить этот результат, но безуспешные. Похоже, что этот результат окончательный.

Сомневаюсь, мне кажется 5,7.

UPD. Если кто будет программу писать, hint: нет разницы бежать ли утке по перпендикуляру к стороне или под углом $\arccos(1/k)$ к ней же в сторону от лисы, если при этом не происходит переход на другую сторону многоугольника. Т.к. при таком наклоне увеличение пути утки строго компенсировано увеличением пути лисы (собственно это и есть определение угла). Зато искать и анализировать перпендикуляр немного проще.

[worm2]

Тоже на секундочку отошёл и удивился количеству сообщений
Я сейчас покопал немного в другую сторону, а именно: возвратился к исходной формулировке с круглыми озером и начальной позицией Утки в центре и озаботился вопросом: как Утка должна плыть на первом этапе, имея целью попадание на "круг безопасности" в противоположной от Лисы точке? Не потребуется ли ей на это бесконечное время (при активном противодействии Лисы)?
Ответ на это получился удивительно простой: в предположении, что первоначальная позиция Лисы — (-1, 0) и она бежит с максимальной скоростью против часовой стрелки, пытаясь максимально оттянуть наступление второго этапа, Утка плывёт по окружности половинного радиуса "круга безопасности" (1/(2k)) с центром в точке (0, 1/(2k)). К тому моменту, как Лиса добегает до (0, -1), Утка как раз попадает к своей начальной точке из самого первого рисунка темы (0, 1/k). В каждый момент времени Лиса и Утка находятся на одном диаметре, т.е. центр озера находится точно на соединяющей их прямой.
Как будет выглядеть первый этап для озёр другой формы — тоже интересный вопрос, вероятно, значительно более сложный.

[Dmitriy40]

worm2 в сообщении #1290080 писал(а):

в предположении, что первоначальная позиция Лисы — (-1, 0) и она бежит с максимальной скоростью против часовой стрелки, пытаясь максимально оттянуть наступление второго этапа, Утка плывёт по окружности половинного радиуса "круга безопасности" (1/(2k)) с центром в точке (0, 1/(2k)).

Простите, сомнительно: угловая скорость утки (относительно центра) не постоянна, в отличии от лисы. Т.е. они не на одном диаметре.
Вот равенство путей вполне допускаю.
Кроме того, давно же вроде известно что внутри круга безопасности утка плывёт по спирали (кажется логарифмической). Если хочет добраться до берега как можно быстрее.
Проверил, был не прав, каюсь.

worm2 в сообщении #1290080 писал(а):

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

Я выкладывал длинный лог перемещений утки и лисы для квадратного озера, там можно посмотреть траекторию утки во втором приближении. Могу даже выцепить оттуда (из 21М текста для мелкой сетки) траектории и нарисовать, придумать бы только в чём это попроще.
И где-то там же говорил про взаимно обратное отображение окружность-квадрат (какое точно не помню, но точно есть), применив которое к траектории утки для круглого озера получим траекторию утки для квадратного (и обратно).

[grizzly]

Dmitriy40 в сообщении #1290078 писал(а):

Т.к. при таком наклоне увеличение пути утки строго компенсировано увеличением пути лисы (собственно это и есть определение угла).

Так возьмите половину этого угла. (Где-то выше я уже объяснял Вам на идейном уровне.)

[Geen]

Dmitriy40 в сообщении #1290078 писал(а):

hint: нет разницы бежать ли утке по перпендикуляру к стороне или под углом $\arccos(1/k)$ к ней же в сторону от лисы, если при этом не происходит переход на другую сторону многоугольника. Т.к. при таком наклоне увеличение пути утки строго компенсировано увеличением пути лисы (собственно это и есть определение угла).

??
Озеро - верхняя полуплоскость, скорость утки 1, скорость лисы 3, утка в точке $(0,1)$, лиса в точке $(-2.9,0)$.
Если утка плывёт по перпендикуляру, лиса её, очевидно, ловит. Если утка плывёт в точку $(0.35,0)$ - то нет (утке надо времени меньше $1.06$, лисе - больше $1.08$).