Слабо решить задачку?

Это ж примитив! Условие:в углу сидит паук а в другом муха це-це, вся комната 3*3 метра сколько расстояния бежать пауку чтобы съесть муху? Ответ:пауку надо преодолеть расстояние 3 метра чтобы съесть муху.

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

Товарищи! Если бы все было так просто, я бы не постил!

(1) Паук сидит не в углу и не на ребре, а на грани.
(2) На заметку, диаметрально противоположная точка не всегда наиболее удаленная.

Зато муха по-любому будет сидеть в углу. И ответ однозначно будет больше 5.

А что паук такой тупой что будет бежать по потолку, стенкам и полу когда можно спокойно пробежать по полу напрямую?!

9^(1/2)+3? максимальное растояние? и оно должно быть всегда одинаково, ибо это куб, а также сказано что муха содится всегда на максимальном расстояний.

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

Сходите, пожалуйста, к Гудвину. Есть такие точки дислокации паука, что муха сядет не в угол и не на ребро.

ой не 9^(1/2) а 18^(1/2)+3

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

По условию одна из координат должна быть 0. А на счет максимального расстояния --- не уверен (скорее всего нет). Максимальное расстояние вычислить трудно.

А ну-ка докажите )

Это при каких координатах паука?

Тоже к Гудвину. Точка, где сядет муха неизвестна.

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

Она сядет на самом дальнем углу от паука (читайте условие, Гудвин)

вот смотри как я рассуждаю, паук поползёт полюбе напрямую, не в обход, и максимальное расстояние будет одна диагональ + одна грань то и есть предположим что паук находится в точке (3,3,3) а муха в (0,0,0) то он проползёт по потолку и слуститя по стене в углу

Он поползет напрямую по двум граням, и его путь будет примерно 6.70. Это самый длинный путь из всех возможных располодений паука и мухи. Но если паук сидит на грани, то его оптимальный путь может пролегать по 4-ем граням!

Нет, не взлетит...

...пауки ведь летать не умеют.

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

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

Как вы себе представляете пересечение пауком 4 граней при оптимальном пути... Максимум 2.

Перебор пишется в два счета, только вот для такого простого условия может есть и не перебор? Конечно, в общем случае минимаксная задача на негладком многообразии это гроб.

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

Или нифига подобного?

>Или нифига подобного?

Угу, это первый из двух переборов. Нужно перебрать 9 вариантов развертки. ДЕВЯТЬ!

Кроме улучшенного перебора с мелким шагом ничего в голову не приходит. :(

Развернуть комнату как картонную коробку и дальше смотреть на развертку.

Децкая задачка. Развертываем куб на плоскость

+--+ | | +--+ | | y +--+ ^ | | | +--+--+--+ | | | | | | +--+--+--+ +-------------->x

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

Пардон косяк с форматированием.

Децкая задачка. Развертываем куб на плоскость

     +--+
     |  |
     +--+
     |  |
y    +--+
^    |  |
| +--+--+--+
| |  |  |  |
| +--+--+--+
+-------------->x

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

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

Обзовём положение на ребре, допустим X .... нет мало... пусть лутше Y... :)

Получаем 2 отррезка длинной 3*(1+Y^2)^(1/2) + 3*(1+(1-Y)^2)^(1/2) == 3*((1+Y^2)^(1/2)+(Y^2-2*Y+2)^(1/2)) .

Обзовём это выражение L(Y).

Теперь от этой хрени нада найти минимум, так шо придеёцца решать уравнение (d/dY)(L(Y))==0

(d/dY)(L(Y)) = 3 * ((1/2)*(1+Y^2)^(-1/2)*((d/dY)(1+Y^2)) + (1/2)*(Y^2-2*Y+2)^(-1/2)*((d/dY)(Y^2-2*Y+2))) == 3/2 * ((1+Y^2)^(-1/2)*(2*Y) + (Y^2-2*Y+2)^(-1/2)*(2*Y-2))

Теперь выясняем при каких Y эта хрень обнуляется:

(1+Y^2)^(-1/2)*(2*Y) + (Y^2-2*Y+2)^(-1/2)*(2*Y-2) == 0

Y +(Y-1)*((1+Y^2)/(Y^2-2*Y+2))^(1/2) == 0

Y/(1-Y) == ((1+Y^2)/(Y^2-2*Y+2))^(1/2)

Y^2*(Y^2-2*Y+2) == (Y-1)^2*(1+Y^2)

Y^4-2*Y^3+2*Y^2 == (Y^2-2*Y+1)*(1+Y^2)

Y^4-2*Y^3+2*Y^2 == Y^4-2*Y^3+2*Y^2-2*Y+1

2*Y==1

Y==1/2

Есть есчё варианты с Y==1 и Y==0

L(0)==3*(1+2^(1/2)) && L(1)==3*(1+2^(1/2))

L(1/2)==3*2*(1+(1/2)^2)^(1/2)=3*5^(1/2)

Очевидно 3*5^(1/2) < 3*(1+2^(1/2))

УСЁ!!!

> +--+ | | +--+ | | y +--+ ^ | | | +--+--+--+ | | | | | | +--+--+--+ +-------------->x

Это тайное послание инопланетянам?

> Нетрудно догадаться, что муха должна сидеть в одном из 6 углов.

бугага

приветствуем члена Чукотского Союза писателей

>бугага

Чё бугагакаешь? В одном из 6 после разверки на плоскость как показано на рисунке. Всего углов 8, два исключаем по ежику понятным соображениям.

А с развёрткой получается тот же результат, но гораздо проще и наглядней.... или не совсем :-/

Слив засчитан.

маршрут движения паука нам не нужен, нужно только расстояние,
поэтому переносим начало коорд в ближайший к пауку угол и заодно разворачиваем куб:
из коорд. паука откидываем одну, которая равна 0 или 3,
остаются скажем a,b;
и выч. коорд. на развёртке : x=min(a,3-a) y=min(b,3-b)

муха сидит либо в 3,9 либо в 9,3 - где дальше, остаётся только вычислить расстояние:
D=max(sqrt((3-x)^2+(9-y)^2),sqrt((9-x)^2+(3-y)^2)

где-то так..сомнения только по поводу новых коорд. паука :)

s/9/6 :)

        x^
         |
    +----+----+----+
    |    |    | *  |
    |  * |    |    |
 <--+----+----+----+-->
 z                    z

Пусть паук сидит в точке (x,0,z) муха - (x1,a,z1) и пусть кратчайшее
расстояние идёт либо по полу (z=0), либо по потолку (z=a).
Тогда расстояние до мухи либо sqrt((x1-x)**2+(z1+z+a)**2) по полу, либо
sqrt((x1-x)**2+(3a-z-z1)**2) по потолку. Эти расстояния
должны быть равны, иначе они будут не максимальны (если
расстояние по потолку больше, чем по полу, то муха может
сесть чуть выше и тем самым увеличить максимальное
расстояние). Решая уравнение, получим r**2=(x1-x)**2+4*a**2,
где x1=0 если x>a/2 и x1=a если x<a/2, т.е.
r**2=max((a-x)**2,x**2)+4*a**2

Ну а далее надо провести обобщение на произвольную грань.
Паук не дурак и побежит по той грани, по которой путь будет
минимальный. Отсюда
r=sqrt(4*a*a+min(max((a-x)**2,x**2),max((a-y)**2,y**2),max((a-z)**2,z**2)))

В общем, от задачи на программирование остались чтение и запись из файла :)

Типа можно тупым перебором, т.к. по условию задачи шибко точного ответа не нужно. Чето типа

static double solve(double x, double y, double z) {
    double x1 = 0.0, y1 = 0.0, x2, y2, r = 0.0;
    if      (x == 0.0 || x == 3.0) { x1 = y; y1 = z; }
    else if (y == 0.0 || y == 3.0) { x1 = x; y1 = z; }
    else if (z == 0.0 || z == 3.0) { x1 = x; y1 = y; }

    for (x2 = 0.0; x2 <= 3.0; x2 += 0.01) {
        for (y2 = 0.0; y2 <= 3.0; y2 += 0.01) {
            r = max(r, min4(
                 dist(x1, y1, x2, 9.0 - y2),
                 dist(x1, y1, 9.0 - x2, y2),
                 dist(x1, y1, x2, -3.0 - y2),
                 dist(x1, y1, -3.0 - x2, y2)));
        }
    }

    return r;
}

max() - максимум из двух чисел, min4() - минимум из четырех чисел, dist() - расстояние между точками.

На данных из примера дает результат 6.139

"Немного полетав, она села в то место, до которого пауку бежать дольше всего."

Максимальное расстояние для куба 3х3х3 будет диагональ одной стороны + 3 метра, то есть примерно 4,24 + 3 = 7,24 метра

Логично предположить, что паук будет бежать по кратчайшему пути. Если паука штырит, то он может побегать по комнате чуток, или оббежать две диагонали, но в принципе 7,24 это максимальное из кратчайших, или кратчайшее из максимальных.

Пояснение к коду выше.
Развертываем куб таким образом:
      +--+
      |FF|
      +--+
      |1 |
+--+--+--+--+--+
|FF| 4|SS|2 |FF|  
+--+--*--+--+--+
      |3 |
      +--+
      |FF|
      +--+

SS - грань, на которой сидит паук. Его координаты (x1, y1).
Для определенности начало системы координат паука в точке, помеченной *.
Ось Y направлена вверх, ось X - направо.

FF - противоположная грань, на которой сидит муха.

Перебираем точки (x2, y2) на грани FF в её собственной системе координат.
Для каждой точки (x2, y2) находим её координаты (x3, y3) в системе координах паука.
4 варианта, как показано на рисунке:
1. (x3, y3) = (x2,        9.0 - y2 )
2. (x3, y3) = (9.0 - x2,  y2       )
3. (x3, y3) = (x2,        -3.0 - y2)
4. (x3, y3) = (-3.0 - x2, y2       )

Кратчайший путь к мухе проходит через одну из соседних с SS граней
Т.е. берём минимум из четырех расстояний между (x1, y1) и (x3, y3).
Максимум из всех кратчайших расстояний будет решением задачи.

Есть подозрение, что это решение самое простое и при этом, вроде, правильное :)

Я именно это предлагал... но вот что насчет путей к мухе проходящих через 4 грани, например SS,3,4,FF? Сверни куб и посмотри, такие путя выглядят вполне разумно в некоторых случаях. Кроме того паукъ сидит на грани, а это несколько сужает задачу, так что предположения членов Чукотского Союза Писателей о том, что муха сидит в углу, начинают выглядеть вполне осмысленно, а это недетски упрощает задачу...
Где же истина?

Если что, то все это в удаленных.

>вот что насчет путей к мухе проходящих через 4 грани, например SS,3,4,FF?

Такого, вроде, не может быть. Для наглядности, чуть изменим развертку: +--+ |1 | +--+--+--+--+ | 2|SS|3 |FF| +--+--+--+--+ |4 | +--+ Очевидно, что путь через SS,3,4,FF всегда дольше, чем SS,3,FF

>...что муха сидит в углу

Фиг знает, может и в углу, но это в случае решения тупым перебором пофигу :)

   +--+
   |1 |
+--+--+--+--+
| 2|SS|3 |FF|
+--+--+--+--+
      |4 |
      +--+

а мне не очевидно...

   +--+
   |1 |
+--+--+--+
| 2|SS|3 |
+--+--+--+--+
      |4 |FF|
      +--+--+

+--+--+--+
|SS| 1| 2|
+--+--+--+
| 2|
+--+
| 3|
+--+
|FF|
+--+

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

+--+--+--+
|SS| 1| 2|
+--+--+--+
   | 2|
   +--+
   | 3|
   +--+
   |FF|
   +--+ 

len = min( sqrt( w*w + 36); sqrt( v*v + 36) )

Где, w и v равны 2 из (x,y,z) с отрброшеной одной равной 0 или 3.
Не работает на примере, и я не могу понять почему. Такое подозрение, что он не корректен.

Удалённые читать интереснее всего.

Но самое интересное в другом. Коллективный разум решает вопрос полёта паука 9 с лишним часов. На олимпиаде на все задачи даётся сколько? Четыре часа? Вопрос - для кого предназначены олимпиады?

А разве тут хоть кто-то всерьёз над этим сел и задумался?

Но разум-то коллективный. Если десять человек будут думать по 15 минут, получим ... ну не 150 минут, но минут 100 эквивалента мыслительной деятельности точно.

Вот к примеру тов. root_at_localhost думал 6 часов. Может, с перерывами, но 6 часов!