Очевидно, что муха пребудет в углу, образованном двумя максимально
 удалёнными от павука гранями и третьей, противоположной ему.
Очевидно также, что кратчайши путь пролегает через одну из этих двух
 максимально удалённых граней.
Развернём куб и оставим только три интересующие нас грани:
    o---+
    |   |
    |   |
    |   |
o---+---+
|   |   |
|   |   |
|   |  x|
+---+---+
o - угл с мухою.
x - павук.

Далее, у павука есть два пути - локальных минимума:
sqrt (x'^2 + (y'+L)^2)
sqrt ((x'+L)^2 + y'^2)
где L - длина грани
x' - в зависимости от значения координат может быть либо x либо L-x.
 (берём максимальное)
y' - тоже самое.
x и y - условные, это две из координат павука,
 которые не равны ни нулю ни L.
Можно вычислить оба значения, и выбрать из них минимальное.
А может быть, можно априори из значения координат вывести,
 какое из них будет максимально. Мне лень это. 

Для олимпиады важен результат, а для ЛОР - сам процесс.

>Очевидно, что муха пребудет в углу

Вовсе не очевидно.

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

Достаточно очевидно. Представь сферу с павуком в центре. Пусть она расширяется. Какая точка будет последней, оставшеся снаружи сферы?

Имеется в виду точка, принадлежащяя кубу.

У меня такая задача была на олимпиаде 8 лет назад. Так что боян.

павук не літак, він не літає.

Тьфу. Павук не лiтак, вiн не лiтае.

Откель ведаеш? Вдрух это анонимный павук-левитатор на торсионном движке из одноимённого треда?

Бывают кстати летающие. Есть ещё которые на паутинках летают. :) Ну и уж все умеют протянуть паутину по ветру и по ней перейти. Хотя наверное в том кубе сквозняков-то нету... :(

В задаче не указана напряжённость торсионного поля - значит предполагаем её нулевой :-)

А если в задаче по физике не указывается величина ускорения свободного падения, ты её тоже считаеш нулевой?

Торсионное поле - поле кручения. Где сказано, что куб крутится? По умолчанию предполагаем, что он покоится или движется равномерно и прямолинейно! И вообще - можёт в нём невесомость! Хотя нет, в невесомости мухи не летают :-(

> Хотя нет, в невесомости мухи не летают :-(

Почему это?

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

Похоже, что тут никто эту задачу не решит. Хотя наиболее близок к решению полным перебором был root_at_localhost.

ЗЫ: На олимпиаде тоже был коллективный разум: в команде 3 человека.

За скромную суму в $100 выпишу полное решение с доказательством в 60 минут.

Причём эту сферу надо чертить на развёртке куба, т.к. по воздуху паук не бегает.

> Похоже, что тут никто эту задачу не решит.

Чем тебе моё решение не угодило?

Да без разницы как, результат одинаков. но я понял "максимальное расстояние" из условия как максимальное расстояние по прямой, ибо ИМХО оно должно быть таковым с точки зрения мухи.

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

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

-------
| |
| |
| |
| |
-------
-------
| |
| y |
| |
| |
-------
------- ------- ------- ------- -------
| | | | | | | | | |
| y | | | | | | | | y |
| | | | | | | | | |
| | | | | x | | | | |
------- ------- ------- ------- -------
-------
| |
| |
| |
| |
-------
-------
| |
| |
| y |
| |
-------

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

Очевидно в этой развертке прямая- кратчайший путь раука до мухи, следовательно окружность наибольшего радиуса,

Упс... Спросонья криво условие прочёл :( Но тогда ведь решение вооббще очевидно. Для координат (x, 0, z) максимально удалённым будет (z, L, x), расстояния-экстремумы до которого - sqrt ((2x-L)^2 + (2L)^2) и sqrt ((2L)^2 + (2z-L)^2). Минимальным будет то, в котором участвует переменная, наиболее близкая по значению к L/2.

>За скромную суму в $100 выпишу полное решение с доказательством в 60 минут.

Я решу за стакан красного и соленый огурец.

>Упс... Спросонья криво условие прочёл

Перечитайте еще раз :). Да и сообщения тоже неплохо было бы просмотреть.

дурной лор, блин чертеж не видно, рост обрезан.

короче развертываем комнату, пол - стена с пауком,

а потолок - на чертеже рисуем 4 раза xx5xx xx3xx 52015 xx4xx xx5xx

где 0 - стена с пауком, 1,2, 3, 4 - стены граничащие с ней, 5- противоположная. точки за которые паук добежит за время не больще t лежат в одном круге.

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

S(потолка) = S(1) + S(2) + S(3) + s(4), где S(i) - плозадь покрытой части развертки. S(i) = S(трапеции(i)) + S(сектора(i)) - S(треугольника(i));

то есть радиус окружности покрывающий потолок можно найти по формуле.

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

Если я не глючу, конечно.

Если надо, вечером подумаю над аналитической формулой в готовом виде (если кто-то опросит и я не ошибся сейчас). Так что задачка решается без перебора =)

опять чертеж кривой :(

> Я решу за стакан красного и соленый огурец.

Да ну... там писать много.

И эти люди рассказывают нам о штрейхбрейхерах. :)

>Если я не глючу, конечно

"Глючите", конечно. (1) не окружности, а дуги (они могут начинаться и заканчиваться не на ребре) (2) и их не 4, а 12.

14 часов...

иопта,

> Для координат (x, 0, z) максимально удалённым будет (z, L, x)

читать как

> Для координат (x, 0, z) максимально удалённым будет (L-x, L, L-z)

В остальном всё верно.

Диаметрально противоположная точка не всегда наиболее удаленная.

Вы заработались, хлебните пивка, поглядите на задачу чуть подольше. :)

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

Нифига. Если павук находится близко к ребру, то муха сядет близко к противоположному ребру.

не понял, какие дуги?

мы проводим окружности с центром в пауке.

почему 12? паук может попасть на потолок только 4 способами.

Эх, пифка бы щяс... Если павук лезёт по одной из стен к мухе с произвольными координатами, квадрат потребного расстояния (x+L+xm)^2+(z-zm)^2. Если по противоположной - (3L-x-xm)^2+(z-zm)^2. При произвольном фиксированном zm, видно, что изменяя xm мы сокращаем одно расстояние и удлиняем другое (x и xm неотрицательны и не могут превышать L). Откуда понятно, что максимальное будет при x+L+xm=3L-x-xm, откуда xm=L-x. Такие же рассуждения проделаем для zm, взяв две другие противоположные стены. И получим искомое (2L)^2+(2x-L)^2.

Ну так и есь. Например если павук пребывает в (0,0,0) то муха - в (L,L,L)

Решение перебором.

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


#include<stdio.h>
#include<stdlib.h>
#include<math.h>

float x,y;

ReadData(FILE *f)
{
float a,b,c;
fscanf(f,"%f %f %f",&a,&b,&c);
if(a<0.001){x=b;y=c;};
if(b<0.001){x=a;y=c;};
if(c<0.001){x=a;y=b;};
return 0;};

float Dist(float x1, float y1, float x2, float y2)
{
return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}

float FindR(float a, float b)
{
float R=20,buf;

buf=Dist(x,y,a,b+6.);if(buf<R)R=buf;
buf=Dist(x,y,9.-a,3.-b);if(buf<R)R=buf;
buf=Dist(x,y,a,-6.+b);if(buf<R)R=buf;
buf=Dist(x,y,-3.-a,3.-b);if(buf<R)R=buf;

buf=Dist(x,y,-b,6.+a);if(buf<R)R=buf;
buf=Dist(x,y,3.+b,9.-a);if(buf<R)R=buf;

buf=Dist(x,y,6.+b,6.-a);if(buf<R)R=buf;
buf=Dist(x,y,9.-b,-3.+a);if(buf<R)R=buf;

buf=Dist(x,y,6.-b,-6.+a);if(buf<R)R=buf;
buf=Dist(x,y,-3.+b,-3.-a);if(buf<R)R=buf;

buf=Dist(x,y,-6.+b,-a);if(buf<R)R=buf;
buf=Dist(x,y,-3.-b,3.+a);if(buf<R)R=buf;
return R;
};

SolveIt(FILE *f)
{
float R=0,buf;

for(int k=0;k<301;k++)
for(int n=0;n<301;n++)
{
buf=FindR(k*0.01,n*0.01);
if(R<buf)R=buf;
};
fprintf(f,"%.3f",R);
return 0;};

main()
{
char* file_write="OUTPUT.TXT";
char* file_read="INPUT.TXT";
FILE *f;
f=fopen(file_read,"r");
ReadData(f);
fclose(f);
f=fopen(file_write,"w");
SolveIt(f);
fclose(f);
return 0;};

Что в моем аналитическом решении не так?

>Что в моем аналитическом решении не так?

Нарисуйте 12 разверток (как в процедуре FindR(...)) проведите окружности, нарисуйте СЕКТОРА (ведь если кусок прямой выходит из развертки, то это уже не самый короткий путь). Поэтому получаются не окружности, а дуги. И линии одинакового расстояния будут с изломами.

Ничего сложного. Надо лишь доказать что муха всегда сядет в углу.

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

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

Beria.

блин, я совсем тупой?

я не понимаю.

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

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

что я не так понимаю?

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

Если нет правильного паука, надо достать правильную муху?

это не будет кратчайшим путем.

паук максимум ползет по 3 граням и паресекает 2 ребра.

Ну так что, взлетит или нет?

Иногда будет. :)