Нужно составить алгоритм

[EvroStandart]

Вот снова понадобилось. Теперь уже больше математичекое решение нужно.


FlatLand pianos are rectangles of various sizes. FlatLand building codes require all turns in corridors to be right angle turns and prohibit ``T'' intersections. You can assume that each portion of a corridor is long enough so that other corners or doors into rooms don't have any effect on getting around a turn. You can also assume that the piano is narrower than the width of any corridor. "

"Note that the piano actually has to turn in the corner, since it can only be pushed or pulled on one of its shorter sides (there are no square pianos). Your team's job is to write a program for a palmtop computer that will determine if a given piano will fit around a corner in a corridor. "


То есть имеем два коридора под прямым углом в виде буквы "Т" и пианино. Дана длинна пианино, ширина пианино, ширина первого коридора, ширина второго коридора. Как вычислить пролезет ли там пианино?

[Trotil]

Сообщение от EvroStandart

Вот снова понадобилось. Теперь уже больше математичекое решение нужно.

То есть имеем два коридора под прямым углом в виде буквы "Т" и пианино. Дана длинна пианино, ширина пианино, ширина первого коридора, ширина второго коридора. Как вычислить пролезет ли там пианино?

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

Этап 0: Подготовительный этап. Вводятся условные обозначения, система координат, начальные условия, базис, по которому можно однозначно восстановить положение пианино в данной с.к., формулы вычисления координат границ пианино.
Этап 1: Движение точки А вдоль прямой x=0.
Этап 2: Движение стороны АВ пианино, упираясь в точку P. Вычисление закона движения точки А.
Этап 3: По закону движения точки А можно восстановить закон движения стороны BC.
Этап 4: Проверка, пересекает ли прямая ВС точку Q? Если не пересекает, то пианино сможет совершить заданный маневр.


Начальное и конечное положение - см. рисунок.

Так как я не владею английским языком, скажите, верно ли я понял условие задачи?

Пусть координаты пианино зависят от времени, поэтому:

A(t): (X_a(t), Y_a(t))
B(t): (X_b(t), Y_b(t))
C(t): (X_c(t), Y_c(t))
D(t): (X_d(t), Y_d(t))

Положение пианино можно однозначно задать координатами точки А и ориентацией пианино (направлением вектора АВ).
Но можно ввести дополнительное ограничение: Пусть точка D будет всегда прижата к нижней стене (в введенной системе координат - это означает, что y_d(t)=0 для любого t). Поэтому можно ограничится только координатами точки А и с соблюдением того, чтобы наше условие всегда выполнялось.

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

cos(phi)=Y_a(t)/|AD|
sin(phi)=(X_d(t)-X_a(t))/|AD|
cos(phi)^2+sin(phi)^2=1
=>
(X_d(t)-X_a(t))/|AD|=sqrt(1-(Y_a(t)/|AD|)^2)
X_d(t)=X_a(t)+sqrt(y^2-Y_a(t)^2)
Y_d(t)=0

Координаты точек B и C нам не понадобятся. (но нам понадобятся уравнения прямых, проходящих через эти точки - они будут выведены позже.)

[EvroStandart]

Я сам немного не точно понял. Наоборот: коридор не может быть типа "Т". То есть, это не два коридора, а один поворачивающий на 90 градусов. Он делится на два по ширине. До и после поворота ширина коридора отличается. Каждый коридор шире чем пианино.
Нужно не вычислять движение, а найти ответ: пролезет или нет.

Я пока дошёл до простого перебора. Ставить отрезок в угол и начинать наклонять получая разные треугольники. отрезок = длине пианино. При каждом наклоне проверять расстояние между другим углом (вокруг которого двигаюсь) и отрезком. Если расстояние больше ширины пианино, зназит ещё не застряли.

А вот без перебора наверно никак....

[Trotil]

Сообщение от Trotil

Этап 1: Движение точки А вдоль прямой x=0.

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

Для точки А: X_a=0, Y_a=и
Для точки D: X_d=sqrt(y^2-Y_a^2), Y_d=0

Для следующего этапа нам потребуется точка B и зависимость ее от точки А.

Уравнение прямой через A и B:
(y-Y_a)/(Y_b-Y_a)=(x-x_a)/(x_b-x_a) (1)
y-Y_a=(x-X_a)(((Y_b-Y_a)/(x_b-x_a))
Поскольку АВ перпендикулярно АD, то
(Y_b-Y_a)/(x_b-x_a)=(X_d-X_a)/(Y_d-Y_a)

Подставляем в (1) - получили уравние прямой, выраженное через координаты точки А.

Можно переходить к этапу 2. Этап самый труоемкий, решение будет дописано позже.
(14:59)

Сообщение от EvroStandart

Я сам немного не точно понял. Наоборот: коридор не может быть типа "Т". То есть, это не два коридора, а один поворачивающий на 90 градусов. Он делится на два по ширине. До и после поворота ширина коридора отличается. Каждый коридор шире чем пианино.
Нужно не вычислять движение, а найти ответ: пролезет или нет.

А вот без перебора наверно никак....

О! Задача упрощается! Теперь этап 2 совсем не нужен - а он самый трудный в расчетах был. Перебор - это конечно хорошо - но долго(понятие конечно относительное). Задача ведь олимпиадная - скорость тоже важна! Можно ведь вывести формулу - а потом просто подсчитать, и все.
Скоро выдам исправленную версию.


Исправленная версия

Итак, если если вы читали, что написано ранее, то это вам покажется сущим пустяком!

Упрощения в связи с новым условием:
X_a(t)=0 - для любого t

Точка A: (0, Y_a)
Точка D: (x_d, 0)

x_d=sqrt(y^2-Y_a^2)

Отсюда в качестве переменной достаточно взять Y_a и Еще нам понадобится Y_с. Ее можно вычислить так:
Y_c^2+(X_d-X_с)^2= BD^2=x^2+y^2 (1)
Из другого треугольника:
(x+y)^2=(X_d+X_c)^2+Y_c^2

Из этих уравнений можно получить, что X_c=xy/2*x_d
Подставляя X_с в любое уравнение, можно получить Y_с.

Уравнение прямой, проходящее через A и D:
(y-Y_a)/(Y_d-Y_a)=(x-x_a)/(x_d-x_a)
(y-Y_a)/(-Y_a)=(x)/(x_d)
y=((-Y_a)/(x_d))(x)+Y_a (2)

Уравнение прямой через В и С:
эта прямая параллельна прямой АD => выразим через (2) и (Y_c)
y2=((-Y_a)/(x_d))(x)+Y_a + 2(Y_c - y_a) (3)

Вот почти и все. у2(a - ширина коридора) - это есть расстояние от нижней стенки до стороны ВС на уровне точки Q (угла стенки). Осталось исследовать эту функцию на max. (пределы исследования: Y_a=y до Y_a=0 - конец маневра)
В программе полученный результат сравнивается с другой шириной коридора) - и программа выдает нужный ответ... Исследование функции на экстремумы проходили в школе, я надеюсь?

PS1: Проверьте вычисления, может где-то ошибка закралась...
PS2: Записывать окончательную формулу в приведенном виде не стал - в режиме текстовой строки прочитать ее довольно трудно. Но здесь просто надо поставить одни формулы в другую и получить искомую формулу...

[EvroStandart]

Trotil:
Для точки А: X_a=0, Y_a=и
Для точки D: X_d=sqrt(y^2-Y_a^2), Y_d=0

Для следующего этапа нам потребуется точка B и зависимость ее от точки А.

Что-то я ничего не понял. Что значит Y_a=и?
Почему для точки D: X_d=sqrt(y^2-Y_a^2)? y здесь какаято длинна, Y_a - координата? А для уравнения треугольника должно быть две длины. И вообще, X_d должно быть тоже координата? Совсем ничего не понимаю...

И в каком месте можно определить, что пианино всё-таки не пролезло? Както это всё слишком запутано....

[Trotil]

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

Начало процесса поворота: t=0
Конец процесса поворота: t=Pi/2

Уравнение прямой CD, выраженное через угол t
y= -x tg(t) – p sin(t) - q/ cos(t)

Запустив цикл по t от 0 до 90° с шагом, например, в 1°, получим семейство уравнений прямой СD при протискивании пианино в углу. В кажом шаге цикла проверим условие пианинного проползания:
y(-a) > -b - если через перебор.

А можно исследовать y(-a) на экстремумы (t=0 до t=90°). Правда это не такая уж и легкая задача будет. Здесь нужно использовать матпакеты и получить приближенное значение(точного решения задача не имеет) и работать уже с ним.

Вообщем, перебором все-таки гораздо проще выйдет.
(копирайт Дин Гиор)
Примечание: вывод формулы:
Коэффициент наклона прямой: k=y_b/(-x_a)=-(p*sin(t))/(p*cos(t))=-tan(t);
Координаты точки D: (-p*cos(t)-q*sin(t),-q*cos(t);
Уравнение прямой: y=y_D+k(x-x_D)
или: y=-q*cos(t)-tan(t)(x+p*cos(t)+q*sin(t))
или: y= -x tg(t) – p sin(t) - q/ cos(t)

[EvroStandart]

Ну, тогда понятно. Я примерно также думал.
Спасибо!

[Trotil]

Сообщение от EvroStandart

Ну, тогда понятно. Я примерно также думал.
Спасибо!

Читай также вот эту тему:
_http://arbuz.uz/forum/index.php?showtopic=1009&st=0
Там подкинули еще одну свежую идейку.