Вы очнулись в глухом лесу. Известно только то, что в лесу нет полянок и площадь леса равна 10км^2. Вам нужно найти наиболее короткий путь, который ГАРАНТИРОВАННО выведет вас из леса. Человека считаем материальной точкой, деревьями пренебрегаем, считаем что человек может идти в любом нужном ему направлении абсолютно точно. Человек тогда выберется из леса, когда расстояние от него до границы леса = 0. Необходимо найти длину пути и указать его траекторию (форму).

было уже

(1) Жаль((

(0) эт фигня, я помню в инсте на физре заблудился с одногруппницей в лесу)

(3) и как, всё получилось?

А в чем тут подвох?
Если других данных нет - идешь прямо и выходишь.

(5) так можешь 100км пройти не выйти

(6) А кругами можно и 200 исходить.

(7) зависит от радиуса круга

взять два дерева провести воображаемую линию до третьего потом дойти до второго и то же самое проделать

(6) "площадь леса равна 10км^2" - это лесополоса какая-то получается, если 100км длиной :)

(0)А радиус видимости у человека какой?

(4) спустя минут 40 мы вышли к спорт-комплексу

айти наиболее короткий путь, который ГАРАНТИРОВАННО выведет вас из леса нереально с такими данными

(11) Радиус видимости нулевой. Лес- непроходимая тайга, в которой может выжить только человек-молекула(материальная точка)

всмысле самый короткий путь нереально. А наиболее короткий - просто идти прямо. и пусть это будет 100 км - радиус видимости 0 если предположить что мы конкретно были у выхода и неверно выбрали направление

(14) Тогда лучше моделировать поведение человека с завязанными глазами в комнате неопределенной формы. Нагляднее.

может быть идти надо по спирали Архимеда

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

(17) с каким шагом?

(17) Кроме того, лес может быть как раз в форме спирали

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

(21) Нулевая видимость = завязанные глаза, не? )))

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

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

(22) (23) уговорили, у него завязанные глаза и внутренний компас, который никогда не врет))

так как площадь леса ограничена - человек гаранированно выйдет из него при любой незамкнутой траектории. А вот окажется ли лес в форме его траектории - это уже дело везения. Так что оптимально просто идти прямо

(0)10 км прямо, потом 10 км на право.

(26) Гарантированно  = с вероятностью раной 1!(стопудова, точно, наверняка, 146%) тут нельзя уповать на удачу

(18) а если лес повторяет оптимальную траекторию, какая разница прямая она или нет?

Если человек материальная точка то он никогда не выйдет из леса. В 10 км^2 сколько угодно материальных точек

А вообще, при таких вводных получается, что самая короткая траектория - круг. Если траектория не замкнута, то под нее можно подобрать такую форму леса, что траектория окажется внутри(лес можно вытянуть вдоль любой незамкнутой траектории и он все равно будет шире траектории, т.к. будет иметь ширину>0,  и траектория(ширина=0) будет внутри леса). Если же траектория замкнута, то внутри пространства обведенного траекторией тоже будет лес(не может быть прогалов и полян).
Соответственно траектория минимальной длины, охватывающая максимальную площадь - окружность.
Ну дальше уже понятно.

(27) А если лес длинный и узкий уголок?

(28) Стопудово выйдешь. Площадь то леса ограничена

(31) радиус легко посчитать для любого наперед заданного эпсилон?)

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

Траектория  - окружность^ R = sqrt(10)/Pi

"олени идут на х.."
в вообще все элементарно, деревья с их мхами в помощь, солнце, звезды и т.д.

(29) Если лес повторяет траекторию (например спираль) - то на нем будут полянки, которых по условию нет.

А как в лесу при видимости ноль пройти по окружности определённого радиуса?

(34) какой-такой эпсилон? ))
какова длина окружности, охватывающей площадь в 10 кв.км?

(39) А это уже второй вопрос)

Во понял, Ходить надо с расширяющими кругами. Поскольку не полян. С каждым кругом площадь леса будет уменьшаться. Остается вычислить с каким шагом.

(28) https://ru.wikipedia.org/wiki/Дельта-функция площадь 1, длина бесконечная, я не знаю как проще объяснить

*(43) к (33)

(40) 11 с копейками километров. Скорей всего окружность и есть правильный ответ. Строим окружность радиусом (10/Pi)^0.5 из текущей точки (текущая точка на окружности).

(29) Это проблемы леса. Через 20 км я гарантированно выйду.

(46) Ох и задолбаешься же ты 20 км по непроходимой-то тайге переть :))))

(28) (43) при ширине леса 0,0002 км его длинна составит 50 00 км, при скорости 6 км/ч поход займёт 248 дней, а за это время человек может умереть с голоду, например

50 000 км

(45) Присоединяюсь.
В (36) формулу неправильно написал (позор на мои седины).

(43) в таком случае остается вероятность что лес будет 1 в 1 совпадать с выбранной траектории и гарантированного способа нет. Длина бесконечная

(46) Не гарантированно же, в (32) контрпример

(49) + Земля в обхвате по экватору 40 000 км и если этот лес расположен на Земле, то он замкнётся и человек никогда не ыйдет

Вообще нам всего-лишь нужно построить замкнутую линию, с площадью описанной области в 10 км. И понятно что минимальную длину будет иметь как раз окружность.

Лес - выпуклая фигура? Если нет то решения нет. Ибо лес может оказаться как раз той формы какой мы выберем путь

(53) Попробуй опиши вокруг экватора лес с площадью в 10 км, и без полянок. У тебя огромные поляны будут на всю площадь южного и северного полушария.

(52) Если рассуждать так, как (32) и при условии что человек материальная точка, то всегда существует вероятность что лес будет расположен в виде линии вдоль его траектории. Поскольку материальная точка и линия не имеют размеров, длина леса становится неограниченной. Получается что человек никогда не выйдет из леса.
А я выйду ;-)

(55) Внимательно прочитай условие.

(57) И ты внимательно прочитай условие.

(59) Нет полянок - это значит гомеоморфна кругу, но не значит что выпуклая

(60) Чего?!

(61) какое слово не понял?

10 км вперед, 10 км вправо, 10 км назад, 10 км влево.
Если за все это время не вышли из леса, значит сделать еще 1 шаг. Иначе - противоречие условию, что нет полянок.

(60) при чем тут выпуклость и односвязанность?

Рисуем окружность, допустим из леса мы не вышли, значит вся окружность находится в лесу. Но так как полянок нет, а окружность замкнута, то значит внутри окружности тоже лес. Значит площадь леса больше 10 км^2. Противоречие.

(63) верно, но есть путь короче

(62) Вот пример невыпуклого без полянок

(63) Это Гарантированный а не наиболее короткий гарантированный

http://ximage.ru/index.php?id=1409319235

(63) буквой Г так сходишь. это надо 10 прямо, 10 направо, ещё 10 направо и ещё 10 направо

(59) А в чем мое утверждение противоречит условиям? Расстояние от материальной точки, до края линии может быть бесконечно велико. Ээээ... т.е. между 0.1 и 0.2 может быть бесконечное число отрезков... как-то так.

1с тоже ходит в лесу, в отличие от SAP, даже менюшки то сверху, по на столе, в такси слева, а какая разница, все равно не работаетю

(71) см. например (65) Мы не можем разместить лес по траектории. Так как в условии написано про отсутствие полянок.

(5) без компаса прямо идти не получится, чаще по кругу получается ))))

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

Идем на север примерно 1,8 км, то есть от центра круга к его краю, затем начинаем идти по кругу с радиусом 1,8 км пока не выйдем. Правда я не знаю, как отмерить эти 1,8 км и как описать окружность. По условиям задачи у нас тока компас...

В (54) полный ответ.

(77) Есть более короткий путь

(76) зачем идти к краю, можно с места начать круг нарезать

(77) а где ж доказательство? и почему замкнутую?
твой ответ - r + 2*Pi*r?
можно меньше...

(77) (73) Согласен.

Pi*r*r=100
Идем по окружности радиуса sqrt(100/Pi)
итого максимум пройдем 2*Pi*sqrt(100/Pi) = 35.44 км

(80) Полное доказательство там будет на несколько листов...

и ответ не r+2*Pi*r, а просто 2*Pi*r

(82) Почему 100?
10 кв.км  же.

Множество точек образующих лес не имеет полянок. Значит для любой замкунтой кривой, все точки которой лежат в этом множестве, все внутри замкнутой кривой, так же лежат внутри леса. Возьмем замкнутую кривую с площадью более 10 км^2. Все точки внутри замкнутой кривой внутри леса лежать не могут, значит есть точка на кривой, не принадлежащая лесу. Если идти по этой кривой, то обязательно выйдешь.
Таким образом задача сводиться к тому, чтобы найти замкнутую кривую с минимальной длиной, и площадью 10 км^2+малая. Вариационной исчисление показывает, что такая минимальная кривая есть окружность радиуса Корень(10/пи) км.
Таким образом, из леса надо выходить по окружности радиусом где то 1.8 км

(84) точно 10 же

(63) (66) Чего-то я не понимаю.. Почему лес не может быть в виде буквы Т?

Лес выпуклый что ли? Где это сказано?

Но (54) пока что выглядит убедительнее всех :)

Траекторией нарисовать восьмёрку и идти из центра. Круги у восьмёрки будут иметь радиус sqrt(50/pi)

(85) У меня 25 надо пройти :)

Идешь прямо 5 км потом двигаешься по окружности  центр которой будет являтся точкой от которой вышел

(0)
Решение: 11 км прямо, если не вышли - потом поворачиваем на 45 градусов и идем 7<X<8 км.

Выходим из леса.

Это фантастика ближе 200 км от любого нас пункта с нас >10000 людей таких лесов с такой площадью нету.... усе вырублено...

(94) То есть остальные условия, типа человека нулевой ширины, тебе показались вполне реальными? ))

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

(95) угу )) ну разные же люди бывают... в том числе и отсутвующие

(92) А кто запрещает сразу начать двигаться по окружности?

(97)Ахах, тогда задача, вообще эпична: как выбраться отсутствующему человеку из фантастического леса по максимально короткой траектории! ))

Сотка!

Отсутствие полянок означает, что лес - односвязное множество на плоскости. В этом случае решение будет в (54). Предлагается рассмотреть ту же задачу, но вместо отсутствия полянок считать лес выпуклым множеством площадью 10км^2. Каким тогда будет ответ?

(101)+ По моему мнению, в случае когда лес - выпуклое множество длина оптимального маршрута будет меньше в корень из 2 раз по сравнению с длиной оптимального маршрута из (54)
Вопрос: каким будет оптимальный маршрут?

Километр прямо, поворот на 90 направо. Километр прямо, поворот на 90 налево.

(102) Это уже слишком сложно.

(102) полуокружность?

+(105) сам я таком ответе сильно сомневаюсь,
но в (102) он похоже предполагается.
Наверное, можно лучше...

Странно, что после (54) ветка все продолжается.

(107) тут после правильного ответа в первом посте может быт несколько страниц флуда
ну а в данном случае в (101) появилась новая версия задачи

..похоже всё-таки правильный ответ на (101) - полуокружность радиусом sqrt(20/pi)
(104) и доказательство ненамного сложнее (54)

(109) Что-то я не уверен ни в первом, ни во втором утверждении.

То есть доказательство что полуокружности достаточно - элементарно. Соединяем концы отрезком, и смотрим площадь. А вот в том что она минимальна - не уверен.

(110) (111) Нужно найти кривую минимальной длины при соединении концов которой, получалась фигура заданной площади.
Достраиваем симметричную кривую относительно этого отрезка и получаем задачу из (0): найти фигуру минимального периметра при заданной площади, только площадь удвоилась

(112) Да, наверно всё-таки полуокружность.

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

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

(115)А если вместо полянок указано, что лес - выпуклое множество, тогда решением будет полуокружность.

(0) сначала подумал, что речь про лес доменов....

ну типа как вариант самый простой для любой более-менее заселённой местности (для районов крайнего севера не прокатит):
1.Ищется река.
2.далее идти/сплавляться по реке - обязательно на НП наткнёшся - вдоль рек их много

ежик в тумане отдыхает

(0) А что если идти по кругу, площадь которого 10 км^2 ? Это будет самый короткий путь?

(117) Есть речки на которых между деревнями 100 км, проще искать лесозащитные просеки, линии высоковольтных передач или дороги.

(120) ЛЭП должны в принципе очищаться но практика показывает что часто там самая непроходимая чащоба... хотя вдоль идти тоже можно... ну и дороги - конечно, если шоссе то возможно ещё и кто подберёт

(116) Вот только если нет полянок, то полуокружность, как уже выше сказали :)

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

Если на форму леса не наложено никаких ограничений, то путь из леса может быть сколь угодно длинным.

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

(98) центр где будет?

(124) ну первоначальную задачу через вероятности только решать возможно, но потом уточнили что лес ВЫПУКЛЫЙ

(126) тогда улиткой надо ему выходить.

(127) дык и выходят улиткой тока такой, слегка квадратной

типа 10км прямо, потом 10км в сторону под 90 градусов

раз площадь 10км^2 то типа всегда выйдем и больше 20км никогда не пройдем ))

(127) А почему не по эвольвенте окружности с радиусом sqrt(10/пи)?

(129) кратчайший нужен, по спирали можно долго ходить если в центре начать и пройти многа больше 20км

(130) Да хоть с центра хоть откуда, ты кривую нарисуй и не факт что квадратная улитка будет выгоднее.

(0)Цитирую -"считаем что человек может идти в любом нужном ему направлении абсолютно точно"
Вот тут у вас закралась явная ошибка. Не может. Поэтому лучше вместо человека выберете какой нибудь другой объект, который действительно может идти в нужном направлении абсолютно точно.

(132) Докопаться до формулировки задачи вместо попытки ее порешать - явно не путь самурая

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

т.е. 20км и не км больше, а у улитки скока максимум?

Если выходить по маршруту
1. Сначала по радиусу = корень (10/пи)
2. потом по окружности с этим радиусом. то выйдет.

собственно длинна =корень(10/пи)(1 + 2*пи).

Можно короче, по улитке но вот как найти ее форму не знаю.

(135) Я и предложил такую, весьма скоро растущую улитку. https://ru.wikipedia.org/wiki/%DD%E2%EE%EB%FC%E2%E5%ED%F2%E0_%EE%EA%F0%F3%E6%ED%EE%F1%F2%E8

(139)Так и я не самурай.

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

(138) А вдруг "лес" вытянут колбасой километров на 50?

(139) а вдруг лес вытянут улиткой и мы как раз по ней пойдем?

(140) Вроде лес выпуклой формы, иначе он и квадратной улиткой может быть вытянут.

(140)+100
Поскольку форма леса неизвестна, нет предопределенной траектории которая заведомо будет короче других.
Поэтому выбираем простейшую - прямая.

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

(141) предвидел ))

поэтому если в (139) лес "вытянут колбасой километров на 50" то его ширина (при площади в 10км^2 и длине 50км) будет какая? и пройдем максимум 10+ширина

(141)Где это написано.

(144) Если нет условий на выпуклость, и нет минимальной ширины, то никакая траекторя гарантированно не выведет из леса. Для тебя пример квадратная улитка.

(146) не не не путай ответ в (144) для выпуклого

(141)Вы первую страницу обсуждения не читали принципиально?
у вас из истинной предпосылки ("Поскольку форма леса неизвестна")следует вывод("нет предопределенной траектории которая заведомо будет короче других"), истинность которого не доказана. а затем, на этой предпосылке(истинность которой неизвестна) вы делаете вывод про прямую линию и считаете его истиной?

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

*(149) Извините, (148) к (142) конечно же

(148)
Ок.
Форма леса не известна - истинность вы подтверждаете.

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

Вы говорите что истинность этого вывода не доказана.
Хорошо, попробуем доказать.

Нам нужно найти путь от нашего местоположения(точка) до границы площади (множество точек)
Как известно из геометрии кратчайшим путем между двумя точками является отрезок прямой ограниченный этими точками.
Значит кратчайшим путем будет самый короткий отрезок из множества отрезков которые можно построить между нашим местоположением и границей.

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

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

(151) Скорее задача звучит немного по другому. Найти минимальную по длине линию произвольной формы, которая гарантировано имеет пересечение с границей "леса без опушек".

(151) Путь в 54 имеет длину от 0 до 5,652 км, по твоему от 0 до бесконечности

ой, от 0 до ~11,304 км

(153)Еще раз - задача найти наиболее короткий путь между точками. А наиболее короткий путь как известно это отрезок прямой между этими точками.
Поэтому какой бы вы ни шли до границы, всегда построить отрезок прямой между вашим местоположением и точкой на границе куда вы вышли, и он будет либо короче, либо равен вашему пути.

(155) а как построить отрезок, если известна только одна точка?

(153) -(154) Откуда эти конкретные цифры? как ты их посчитал?

(155) Еще раз, основная цель задачи в (0) выделена БОЛЬШИМИ_БУКВАМИ СПЕЦИАЛЬНО_ЧТОБЫ_ИСКЛЮЧИТЬ_САМОСТОЯТЕЛЬНЫЕ_ДВУСМЫСЛЕННЫЕ_ФОРМУЛИРОВКИ

(156)Никак. Поэтому найти кратчайший путь невозможно.
О чем я собственно и сказал в (142)

(158)В (0) большими буквами выделено слово "гарантированно"
Так вот отрезок прямой это путь который гарантированно выведет вас из леса.
А чтобы узнать кратчайший он или нет нужно знать множество других отрезков прямой соединяющих ваше местоположение с границей леса.

http://itunesboss.com/?ref=pD3oEH5ab

(157) из (54)Вообще нам всего-лишь нужно построить замкнутую линию, с площадью описанной области в 10 км. т.е. сплошной лес площадью 10 км2 не сможет полностью заполнить круг площадью больше. мы идём по окружности площадью 10 км2. Радиус такой окружности ~1,8 км, а длина 11,304 км

(160) прочтите (43) и поймите, что бывают БЕСКОНЕЧНЫЕ прямые единичной площади

(160) Так вот окружность ГАРАНТИРОВАННО выведет через 11,304 км, а вот прямая не факт

другой траектории, которая ГАРАНТИРОВАННО выведет быстрее нет

(163)Ага ну давайте к этой задаче применим неевклидову геометрию, или вообще выйдем из плоскости в пространство...
Не смешно.

(164)Объясни пожалуйста почему ты решил что окружность гарантированно выведет через 11,03км?
Путем каких расчетов?

(166) Да и по евклидовой, лес шириной 1 м имеет длину 10 000 км(при площади 10 км2). Вполне Евклидово

(167) потому что такую окружность нельзя вписать в лес площадью 10км2 любой формы, где-то она будет выпирать, т.е. идя по окружности ходок пересечётся с краем леса, т.е. выйдет из него

(167) S круга = Пи*r2(радиус в квадрате)
нам нужен круг S=10, ищем радиус

r=корень из 10 / Пи = 1,78 км, нем нужна величина больше, для ровного счета 1,8 км

ищем длину такой окружности = 2*Пи*r = 2*3,14*1,8= 11,304 км

(170)А если он будет топать по прямой, то гарантированно выйдет за 10км.

(171) почему? см (168)
лес шириной 1 м имеет длину 10 000 км. Можно по прямой 10 000 км топать, если 0,5м то 20 000 км топать

(171) Не гарантированно, при условии что форма леса неизвестна. Не исключена ошибка в определении верного направления.

(173)В любом направлении.

(172) Опровергает твоё заключение, можно и несколько тысяч км протопать

(175)Ну если таким образом опровергаете мое заключение, то я сейчас этим же способом опровергну ваше, насчет окружности :)

(176) Не выйдет, ибо площадь леса будет больше заданной или появистя "опушка".

(177)Какая опушка?

Если так рассуждать -
У вас окружность длиной 11,304

Берем две окружности одна длиной 11,3039 другая длиной 11,3039.
Между ними свободно вписывается ваша окружность, а вот лес по площади не влазит.

ой блин одна длиной 11,3039 другая длиной 11,3041.

(180) Внутри твоего леса в виде кольца имеется опушка (пустая область), запрещённая условиями задачи в (0)

(181)Лес расположен между двумя окружностями, и ограничен этими окружностями.
Внутри границ леса нет никаких полянок, за границами сколько угодно в обе стороны.

(182) граница должна быть одной линией, иначе будет полянка.

(183)Еще раз - площадь леса это кольцо ограниченное двумя окружностями. Можешь обойти всю площадь в пределах границ - ни одной полянки ты не найдешь.

(184) У тебя область леса ограничена двумя границами, значит есть полянка.

(182)Найти путь который выведет вас из леса. Человек тогда выберется из леса, когда расстояние от него до границы леса = 0

Т.е. когда человек доходит до внутреннего границы леса, но по факту из леса не вышел он должен выпадать в BSOD?))

в  (0)  нет полянок =  https://ru.wikipedia.org/wiki/Односвязное_пространство

(185) + Иными словами лес это односвязная область.

(186)Человек тогда выберется из леса, когда он будет находится не в лесу и расстояние до границы леса будет больше 0.

(187)При чем тут односвязное пространство? Каким боком оно тут?
В (0) о нем ничего не сказано?

(189) Это и есть формальное определение наличия полянок.

Так насчет окружностей

1. Какой радиус у круга площадью 10км^2 ?

2. А какой радиус у полукруга (половины круга) такой же площади?

И скоко скоко мы пройдем по окружности если стартанули в самом неудачном случае в 2 - т.е. идем по сути вдоль окружности внутри

(185)Вот именно территория леса ограничена границами, и в пределах границ нет ни единой полянки.
НЕ БЫЛО НИ ЕДИНОГО РАЗРЫВА!
:))

(195) Тебя клинит. В центре леса огромная поляна.

(194) -> (193)

(191)Ага, озвучь пожалуйста общепринятое формальное определение полянки.

(194) У него это не поляна, а "не лес". онятно что условия задачи с точки зрения формальной математики немного расплывчато определены.

(194)Нет, что ты, центр леса будет где угодно но между границ.

(196) Лес без полянок односвязная область на плоскости.

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

(199)Докажи.

(200) тогда твоё формальное определение "полянки"
(201) Что доказать?

(192) В смысле неудачном. Откуда стартанули - оттуда и иди, через 11,304 гарантированно выйдешь. Пройдя эту окружность из любой точки леса ты гарантированно из него выйдешь.

(202)
Мое определение полянки - территория на площади занимаемой лесом, которую нельзя назвать лесом.
Так пойдет?

Докажи что лес без полянок это односвязная область на плоскости.

(200) С таким подходом полянок вообще нет: есть либо лес, либо  то, что "я не рассматриваю".

(205)А чем плох подход?
В (0) сказано только про лес и его площадь.
Вот я и рассматриваю только площадь занимаемую лесом.
О том что там за границами леса твориться в(0) не сказано.
А в пределах границ леса, я гарантирую отсутствие полянок :)

(204) Что такое пустота внутри твоего кольца? Или она не в лесу. Тогда как определить выход из леса, ибо внешня сторона кольца тоже "полянка", только чуть больше чем сам лес.
Это определение "леса без полянок" — односвязная область. Все остальные конфигурации леса — с "полянками" внутренними или внешними.

(206) Берем любой лес, и говорим что в нем нет полянок, а полянки - за границами леса.

(208)А почему нет? Форма леса неизвестна. Топикстартер вроде это не отрицает.
Так почему бы не выбрать именно такую причудливую форму? Я не вижу запрета в условиях задачи.

Условия задачи поставлены достаточно нечетко, и позволяют мне такие вольности.

(209) Тогда та задача которую видишь ты - не имеет решения, а задача которую видят все остальные - имеет достаточно простое решение.

Известно только то, что в лесу нет полянок и площадь леса равна 10км^2. Толковать как лес представляет собой односвязную область на плоскости площадью 10 кв. км.

(211)Согласен.
Но что плохого в том, что я смотрю на задачу не так как остальные?

(213) то что ты не выйдешь из леса

(212)Я выше привел пример леса без полянок, который не является односвязной областью.

(214)Почему это?
Еще как выйду.

(209) рассмотри лес состоящий из концентрических окружностей с рациональными радиусами вокруг тебя

(216) Вдоль любого твоего маршрута строим лес шириной 0. И говорим что полянок нет. Как же ты выйдешь?

Или даже шириной не ноль, а шириной 1/(длина твоего маршрута)

(216) если по твоему решения нет, то как ты выйдёшь?

(215) тогда можно будет двух- или более связной областью охватить любую кривую конечной длины и утверждать что она из леса гарантированно не выводит. То есть задача не будет иметь решния

(221)Вот. Именно об этом я сказал еще в (142).
Единственный гарантированный выход из леса это кривая.

упс..
Прямая разумеется.

(222) Ну и? Лес точь-в-точь повторяет форму твоей кривой. И как же ты выйдешь?

(83) да там, условия немного отличалось от сабжа:
площадь леса неопределена, но известно, что в 10км от текущего местонахождения находится шоссе (прямая дорога)...

(223) Лес - прямая. И как-же ты выйдешь? Через сколько километров, не подскажешь?

Т.е только идя по прямой можно гарантированно выйти из леса.
А по кривой можно гулять как угодно долго, если не повезет.

(225) ну это совсем легко, значит нужно обойти все равноудалённые точки, а это окружность. Тут даже считать ничего не нужно

(226)В условии задачи  оговорена площадь леса.
Т.е она конечна.
Поэтому в конце концов выйду.

да надо идты па кругу

с радиусом чуть больше чэм радиус круга площадью 10км^2

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

))

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

(229) шира леса ноль целых шиш десятых или чуть меньше. Так чтобы охватить твою прямую.

Поэтому господа послушайте совет человека который неоднократно ходил по лесу - никогда не ходите по лесу кругами если хотите выйти! Только по прямой.

(233) Вот только не все могут идти по сплошному лесу прямо.

(232)Да без разницы, главное что площадь леса конечная величина.

(235) то есть по лес в виде дельта-функции вас не переубедил?

(234)Скажем так - никто не может идти по сплошному лесу прямо.
Не получается.
Поэтому надо уметь ориентироваться чтобы выдерживать максимально  прямой маршрут с помощью внешних ориентиров

(236)Ни сколько.

Это был очень странный лес, сначала я ходил за грибами, потом они за мной)

(237) А лучше по компасу и карте, но тогда считать ебя заблудившимся сложно. Хотя некоторым и такое удавалось, ибо не могли сориентировать километровку, впрочем это достаточно непросто.

(240)Карта уже роскошь.
А  не суметь сориентировать километровку запросто. Был бы лес хороший, да погода плохая.
Человек может эффективные кругаля давать на пятачке радиусом метров в сто.
http://www.youtube.com/watch?v=MLIT647K0zE&list=UUbJQ5QEAfyRNO7t5gpWfuDQ

(241)Я сам зимой на одной из речек "просчитал" поворот и промахнулся с выходом к машине на километра полтора да ещё и вышел с другой стороны. Хорошо хоть основной ориентир "качалки" виден был со всех сторон. и деревня в округе только одна.

А ведь Jump прав - у леса может быть 2 границы и ни одной поляны. Н., в горах есть нижняя и верхняя граница леса, а вершина - это не поляна.

(243) Нет по условиям в (0) граница у леса одна, а то что внутри это поляны

Т.е. если лес в виде кольца (по топологии) то пустое пространство внутри это поляна по сути...

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

(243) а если вершину украдут, появится поляна, и если принесут обратно, она уже не пропадет. уличная магия

(244)Дело в том что в условиях задачи этого четко не оговорено.
Поэтому это лишь ваше мнение, вполне такое правильное мнение.
Но надо понимать что могут быть и другие мнения, и не менее правильные.

(246) Спасибо что поделился своей мудростью, сенсей, мы запомним этот урок

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

(246) Специально для вас, видимо, нужно постить задачки только в кванторах

(248) По этому она находится в секции Математика и алгоритмы

(248) Теорема о существовании точной верхней и нижней границы множества, вообще не имеет никакого отношения к реальным границам реальной территории.

9.99999 км прямо и поворот налево/направо под прямым углом, oneass'ники млин

хотя если лес в форме Г, и т.д то прощще по спирали идти

а если лес в форме спирали и мы как то пойдем как раз по ней, то тогда по по окружности диаметром 10км

+(254)не 10, а 9.99999

хм. а если лес в форме окружности и с дорожкой от центра к этой окружности и мы каким то макаром пошли по этой дорожке.. ппц.. беру слова назад про oneass

Если идем с места на котором стоим в любую сторону так, чтобы наш путь лежал по окружности площадью 10кв2. (у нас суппер точный GPS). В самом нелепом случае, мы дойдем до того-же места где стояли. И выйдем из леса на последнем шаге, т.е. мы попали в абсолютно круглый лес и топали ровно по окружности его(при этом какая-то малая величина была между нами и НЕЛЕСОМ), и значит после замыкания окружности, делаем 1 шажок наружу и оппачки мы вышли.

Ответ длина пути:11,304 а траектория окружность.

(Не буду разжевывать зачем в задаче упомянуты "поляны", думаю это очевидно.)

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

(258) Тор- это недопустимая фигура по условию задачи. В лесу нет полянок.

(257) молодец (54)(82) только вместо 100 - 10 км

(253) даже если он прямоугольный 11 на 0,9(09) км, то не выйдешь

(259)Я приводил выше форму леса в виде кольца, там тоже нет полянок.

(262) Это который лес вокруг горы?

НУ ДА стакан может быть наполовину полон, а может наполовину пуст...

Если внутри линии внешней границы леса есть (рассматриваем обычную евклидову геометрию на плоскости) есть пространство без деревьев то это и есть поляна.

(228) было б легко, если б это был правильный ответ

Эка завернул "внути линии внешней границы"
Все проще - берем площадь леса ограниченную границами, и ищем там поляны. А полян там нет. А за границами леса много чего может быть :))

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

(266) ага специально написал про внешнюю границу )) т.к. у рассматриваемого в (0) леса граница только одна (нет полян) и пофиг насколько он выпуклый

(266)А у него и нет внутренних границ.
Есть граница, которая отделяет территорию леса указанной площади, а что там за границей мне неведомо.

Откуда там поляна? Я вообще не пойму.

Вот еще вариант - узкая полоска леса огибающая землю по экватору. Там тоже поляны есть?

(269)Этот пример был выше. Две больших поляны: одна включает в себя северное полушарие и вторая - южное. Фактически в задаче требуется, чтобы лес был односвязным множеством.
Кроме того, в ветке обсуждался другой вариант задачи. Предположим, что лес - выпуклое множество. Решение тоже в ветке есть и оно отличается от случая, когда лес - односвязное множество.

Фигасебе вас унесло. А я всегда думал, что в лесу надо стараться всё время спускаться, пока не попадётся ручей и далее вниз по течению пока не встретится село. Оно может не математически, за то действенно. Но судя по здешним баталиям в лес нам, обычным смертным, лучше не ходить)))))))))

(0)В этой ситуации самый короткий путь - определить сторону квадрата площадью 10 кв км и идти в любую сторону на длинну одной стороны, если выход не достигнут - повернуть под 90 градусов в любую сторону и продолжить путь.
Все.

(272) А если на угол пойдёшь, оно же дальше чем до ребра то будет. Подумаешь, что ребро не нашёл и на 90 градусов, в сторону следующего угла

(272)Лес может оказаться в форме буквы "Г"

(274)+ Если упереться рогом и обойти квадрат по периметру, то это будет выходом из леса. Но путь будет не самым коротким.

(275) Короче круг обойти, с чего и начали разговор

(269) "узкая полоска леса огибающая землю по экватору" - ну очень очень узкая с площадью то 10 км^2 )) и это уже не евклидова геометрия а на шаре...

(0) А летать можно?

(278) нет, на плоскости летать нельзя. (277) рассчитывается в одно действие - 25см

(279) лес из сильно карликовых деревьев? типа хвоща ))

(270)В (0) про односвязное множество ни слова не сказано.
С чего это лес должен быть односвязным?

А про две поляны порадовало.
Значит берем обычный лес - в форме квадрата например - получается лес и одна большая поляна?

(281) Если пуститься в глубокомысленные рассуждения, то и твое утверждение из (227) "Т.е только идя по прямой можно гарантированно выйти из леса." может не сработать, например, если лес растет в виде цилиндра и ты начал двигаться параллельно границам этого цилиндра.

(282)Задача вроде про плоскость. И на плоскости именно прямая гарантированно выведет из леса.
На объем я перешел чтобы продемонстрировать неправильность рассуждения о полянах за границами леса. Не помогло.

(283) Но ведь в задаче не написано, что пространство - Евклидово, поэтому я взял пространство в виде цилиндра и на нем плоскость.
Не нравится - берем пространство в виде шара с площадью поверхности в 10 кв. км. и на нем лес...

(284)Ну и в чем проблема? Прямая тоже выведет.

Правда в случае пространственных объектов и прямой придется иметь дело уже с верхней границей леса :)

ветку не читал, идти по дуге окржности, радиусом 5 км - было?

(0) Идти на север по мху на деревьях. Если местность незнакомая, то найти ручей, по нему выйти к реке, по реке выйти к деревне.

(285) Куда выведет? Если пространство представлено сферой с площадью поверхности в 10 кв.км., то вся поверхность этой сферы будет покрыта лесом.

(289)Приложи к сфере прямую и посмотри :)

А еще можно представить себе лес как трехмерное множество или четырехмерное множество. Можно еще сюда присобачить путешествия во времени, зеленых человечков и т.д.
Но интерес представляют только такие математические модели, в которых задача имеет нетривиальное решение.
1)лес - односвязное множество на плоскости,
2)лес - выпуклое множество на плоскости.

(291)+ Кого интересуют решения для моделей 1) и 2), выше в ветке они есть.

кстати
если рассматривать интересные варианты
берем небольшой астероид площадью ровно 10 км^2
засаживаем лесом
отправляем всех желающих попытаться оттуда выйти

(291)задачи, которые гарантированно имеют решение, решать не настолько интересно, как ломать им условия

кстати следующий вариант стандартных условий - "в лесу не более N полян"
для вариантов 1, 2(выпуклая внешняя граница)

Запуск энного колва спутников для установления межгалактического контакта с инопланетными разумными существами и проведения вселенского совещания по решению задачи для 5 класса не предлагалось?:)

(265)С каких пор забор на поляне, превращает поляну в неведанную зону?:)

(296)кооператив озеро гарантирует

Какой ответ то?
Полукруг?

(0) Нефиг шастать в лесу по обкурке

(298)
1)Окружность, ограничивающая площадь 10км^2,
2)полуокружность, которая вместе с диаметром ограничивает площадь 10км^2

(300)+ Пункты 1) и 2) из (291)

(300) Так.. Если лес это односвязное, но не выпуклое множество, то полуокружность не подходит? Почему?

(302)Потому, что такой лес может иметь форму буквы "С"

(303) Так траектория то замкнута (граница полукруга)

(304)В случае 2) траектория не замкнута

(305)+ В случае 1) граница полукруга не подходит потому, что это не будет не самый коротний маршрут