e-olymp 13. Паук и муха

Задача

В пустой прямоугольной комнате размерами [latex]A \times B \times C[/latex] (длина, ширина, высота) на пол упала уснувшая муха. Паук, находившийся на одной из стен, или на полу комнаты, начал двигаться к ней по кратчайшему пути.

На какое расстояние он при этом переместится?

Входные данные

В первой строке заданы размеры комнаты [latex]A[/latex], [latex]B[/latex], [latex]C[/latex]. Во второй строке — координаты мухи [latex]X_1[/latex], [latex]Y_1[/latex] и паука [latex]X_2[/latex], [latex]Y_2[/latex], [latex]Z_2[/latex].

Все входные данные — целые числа, не превышающие 500.

Выходные данные

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

Тесты

Входные данные Выходные данные
$3$ $4$ $8$

$0$ $0$ $3$ $4$ $0$

$5.00$
$2$ $2$ $8$

$1$ $1$ $2$ $1$ $4$

$5.00$
$6$ $4$ $3$

$5$ $1$ $0$ $2$ $1$

$6.08$
$30$ $60$ $27$

$13$ $21$ $8$ $0$ $17$

$38.33$
$40$ $40$ $40$

$10$ $5$ $8$ $40$ $37$

$72.03$

Код программы

Решение задачи

Суть решения задачи заключается в переходе от трехмерного пространства комнаты к двумерному с помощью «развёртки» комнаты на координатную плоскость.

Переведя координаты паука в комнате в его новые координаты в двумерном пространстве, все, что нам остается сделать — вычислить кратчайшее расстояние между двумя точками на плоскости с помощью функции [latex]distance[/latex].
В простейшем случае, если паук находится на полу комнаты, т.е. его координата [latex]Z_2[/latex] нулевая, координаты паука [latex]X_2[/latex] и [latex]Y_2[/latex] в точности описывают его положение в координатной плоскости развёртки, и преобразовывать их не требуется.
В противном случае отдельно рассматриваем варианты расположения паука на каждой из стен. В зависимости от того, на какой стене он находится, мы изменяем координаты в соответствии с развёрткой комнаты и находим расстояние от паука до мухи с помощью функции [latex]distance[/latex].
В случае местонахождения паука в каком-либо из углов комнаты, но не на полу, мы должны рассмотреть два варианта его положения в развёртке и найти минимальное из них.

Ссылки

Условие задачи на сайте E-Olymp
Код решения задачи

Related Images:

Mif 14

Задача:

Пересекаются ли отрезки. Для двух отрезков [latex]AB[/latex] и [latex]CD[/latex], заданных целочисленными координатами вершин в трёхмерном пространстве, определить имеют ли они общие точки.

Входные данные:

Координаты отрезков [latex]AB[/latex] и [latex]CD[/latex]:

[latex]A(x_1;y_1),B(x_2;y_2),C(x_3;y_3),D(x_4;y_4)[/latex].

Выходные данные:

Расположение отрезков [latex]AB[/latex] и [latex]CD[/latex] относительно друг друга:

  1.  Прямые в разных плоскостях,
  2.  Прямые параллельны,
  3.  Отрезки находятся на одной прямой но не совпадают,
  4.  Отрезки совпадают,
  5.  Отрезки пересекаются,
  6.  Отрезки не пересекаются;

Тесты:

Координаты

[latex]A(x_1;y_1)B(x_2;y_2)C(x_3;y_3)D(x_4;y_4)[/latex]
Расположение отрезков
1 1 1 1  2 2 2  0 5 0  2 6 -1 Прямые в разных плоскостях
2 1 1 1  -1 -1 -1  0 0 -1  2 2 1 Прямые параллельны
3 1 1 0  2 2 1  4 4 3  5 5 4 Отрезки находятся на одной прямой но не совпадают
4 0 0 0  3 3 6  2 2 4  5 5 10 Отрезки совпадают
5 0 0 0  1 1 1  0 1 1  0 -1 -1 Отрезки пересекаются
6 0 0 1  1 1 1  5 -2 5  4 -1 4 Отрезки не пересекаются
7 1 0 0  1 1 0  0 0 1  1 0 1 Прямые в разных плоскостях
8 1 1 0  1 1 5  2 4 -1  2 4 1 Прямые параллельны
9 1 1 0  2 1 0  5 1 0  6 1 0 Отрезки находятся на одной прямой но не совпадают

 

10 -1 -1 -1  1 1 1  0 0 0  2 2 2   Отрезки совпадают
11 1 1 4  2 2 4  2 1 4  1 2 4 Отрезки пересекаются
12 1 0 3  1 3 3 2 2 3  4 4 3 Отрезки не пересекаются

Алгоритм решения:

Для решения задачи нам понадобятся следующие функции:

1.[latex]Mixed[/latex] — функция возвращающая значение смешанного произведения векторов

(Основная формула [latex]a_xb_yc_z+a_yb_zc_x+a_zb_xc_y-a_zb_yc_x-a_yb_xc_z-a_xb_zc_y [/latex])

2.[latex]Collinear[/latex] — функция принимающая координаты векторов, задаваемых отрезками, и возвращающая логическое значение true, если они коллинеарны, и false в противном случае.

(Основная формула [latex]\frac{a_x}{b_x}=\frac{a_y}{b_y}= \frac{a_z}{b_z}[/latex]  )

3.[latex]VectorEquation[/latex] — Функция принимающая координаты двух точек принадлежащих разным прямым и координаты направляющего вектора, и возвращающая логическое значение true, если они принадлежат одной прямой, и false в противном случае.

(Основная формула [latex]\frac{x — x_0}{V_x} =\frac{y — y_0}{V_y} = \frac{z — z_0}{V_z}[/latex] )

4.[latex]Min[/latex] — возвращает минимум двух чисел.

5.[latex]Max[/latex] –  возвращает максимум двух чисел.

6.[latex]CollinearforPerp[/latex] — функция принимающая координаты векторов, и возвращающая логическое значение true, если они коллинеарны, и false в противном случае. Используется в случае для формулы коллинеарности [latex]\frac{a_x}{b_x}=\frac{a_y}{b_y}= \frac{a_z}{b_z}[/latex] при [latex]b_x=0[/latex] , [latex]b_y=0[/latex] или [latex]b_z=0[/latex].

(Основная формула [latex]a_yb_z-a_zb_y = a_zb_x-a_xb_y = a_xb_y-a_yb_x = 0[/latex] )

Для удобства, заведем переменные для координат векторов соответствующих отрезкам. Первая проверка определяет чему равно смешанное произведение векторов. Если произведение равно [latex]0[/latex] то  векторы находятся в одной плоскости, в противном случае — в разных.

Далее проверяем является ли какой либо вектор перпендикулярным какой-либо оси. Это необходимо так как в таком случае координаты вектора [latex] \vec{CD}[/latex] равны нулю, что недопустимо при делении функций на координаты данного вектора.

В случае если какой либо вектор перпендикулярный какой-либо оси, проверяем их коллинеарность по формуле [latex]CollinearforPerp[/latex]:

[latex]a_yb_z-a_zb_y = a_zb_x-a_xb_y = a_xb_y-a_yb_x = 0[/latex]

 

Если векторы коллинеарны то они параллельны в том случае, если координата вектора перпендикулярного некой оси не равна координате другого вектора той же оси [latex](X_c=X_d and X_a \neq X_c)[/latex] [latex]||[/latex] [latex](Y_c=Y_d and Y_a \neq Y_c)[/latex] [latex]||[/latex] [latex](Z_c=Z_d and Z_a \neq Z_c)[/latex] . В противном случае прямые совпадают. Отрезки также совпадают если одна из координат одного отрезка находится между большим и меньшем значением координат другого отрезка, для всех осей:

[latex](Min(X_a,X_b)[/latex] [latex]\le[/latex] [latex]X_c and Max(X_a,X-b)[/latex] [latex]\ge[/latex] [latex]X_c)[/latex] [latex]||[/latex] [latex](Min(X_a,X_b)[/latex] [latex]\le[/latex] [latex]X_d and Max(X_a,X_b)[/latex] [latex]\ge[/latex] [latex]X_d)[/latex] [latex]||[/latex] [latex](Min(X_c,X_d)[/latex] [latex]\le[/latex] [latex]X_a and Max(X_c,X_d)[/latex] [latex]\ge[/latex] [latex]X_a)[/latex] [latex]||[/latex] [latex](Min(X_c,X_d)[/latex] [latex]\le[/latex] [latex]X_b and Max(X_c,X_d)[/latex] [latex]\ge[/latex] [latex]X_b)[/latex]

 

В противном случае отрезки находятся на одной прямой но не совпадают.

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

[latex](Min(X_a,X_b)[/latex][latex]\le[/latex][latex]X_c and Max(X_a,X_b)[/latex] [latex]\ge[/latex] [latex]X_c)[/latex] [latex]||[/latex] [latex](Min(X_a,X_b)[/latex] [latex]\le[/latex] [latex]X_d and Max(X_a,X_b)[/latex] [latex]\ge[/latex] [latex]X_d)[/latex] [latex]||[/latex] [latex](Min(X_c,X_d)[/latex] [latex]\le[/latex] [latex]X_a and Max(X_c,X_d)[/latex] [latex]\ge[/latex] [latex]X_a)[/latex] [latex]||[/latex] [latex](Min(X_c,X_d)[/latex] [latex]\le[/latex] [latex]X_b and Max(X_c,X_d)[/latex] [latex]\ge[/latex] [latex]X_b)[/latex]

 

Если же ни один вектор не перпендикулярен ни одной оси, проверяем вектора на коллинеарность стандартным способом ([latex]\frac{a_x}{b_x}=\frac{a_y}{b_y}= \frac{a_z}{b_z}[/latex])

Для коллинеарных векторов используем функцию VectorEquation которая возвращает логическое значение true, если точка одного отрезка принадлежит прямой другому, и false если векторы перпендикулярны. Проверка на совпадение отрезков проводиться аналогично первому случаю.

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

 

Ссылка на код программы

Ссылка на условие задачи

Related Images: