Вы очнулись в глухом лесу. Известно только то, что в лесу нет полянок и площадь леса равна 10км^2. Вам нужно найти наиболее короткий путь, который ГАРАНТИРОВАННО выведет вас из леса. Человека считаем материальной точкой, деревьями пренебрегаем, считаем что человек может идти в любом нужном ему направлении абсолютно точно. Человек тогда выберется из леса, когда расстояние от него до границы леса = 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) граница полукруга не подходит потому, что это не будет не самый коротний маршрут