e-olymp 74. Паук и муха — 2

Задача

В пустой прямоугольной комнате длины [latex]А[/latex], ширины [latex]В[/latex] и высоты [latex]С[/latex] муха упала на пол и уснула. Паук, находящийся на одной из стен, или на полу, или на потолке, начал двигаться к ней по кратчайшему пути.

spayder-and-fly-2-task

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

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

В первой строке заданы размеры комнаты [latex]A[/latex], [latex]B[/latex], [latex]C[/latex]. Во второй строке – координаты мухи на полу [latex]X1[/latex], [latex]Y1[/latex], [latex](0 ≤ X1 ≤ A[/latex], [latex]0 ≤ Y1 ≤ B)[/latex]. В третьей строке – координаты паука [latex]X2[/latex], [latex]Y2[/latex], [latex]Z2[/latex], [latex](0 ≤ X2 ≤ A[/latex], [latex]0 ≤ Y2 ≤ B[/latex], [latex]0 ≤ Z2 ≤ C)[/latex]. Все входные данные – целые не отрицательные числа, не превосходящие [latex]500[/latex].

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

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

Тесты

Входные данные Выходные данные
[latex]A[/latex] [latex]B[/latex] [latex]C[/latex] [latex]X1[/latex] [latex]Y1[/latex] [latex]X2[/latex] [latex]Y2[/latex] [latex]Z2[/latex] [latex]S[/latex]
[latex]4[/latex] [latex]7[/latex] [latex]3[/latex] [latex]2[/latex] [latex]1[/latex] [latex]3[/latex] [latex]7[/latex] [latex]2[/latex] [latex]8.06[/latex]
[latex]145[/latex] [latex]26[/latex] [latex]306[/latex] [latex]12[/latex] [latex]24[/latex] [latex]0[/latex] [latex]0[/latex] [latex]305[/latex] [latex]309.34[/latex]
[latex]26[/latex] [latex]18[/latex] [latex]53[/latex] [latex]24[/latex] [latex]15[/latex] [latex]24[/latex] [latex]1[/latex] [latex]53[/latex] [latex]58.52[/latex]
[latex]89[/latex] [latex]89[/latex] [latex]189[/latex] [latex]12[/latex] [latex]24[/latex] [latex]0[/latex] [latex]89[/latex] [latex]16[/latex] [latex]70.77[/latex]
[latex]18[/latex] [latex]26[/latex] [latex]145[/latex] [latex]14[/latex] [latex]2[/latex] [latex]17[/latex] [latex]26[/latex] [latex]141[/latex] [latex]147.14[/latex]

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

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

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

  1. Паук находится на полу ([latex]Z_2 = 0[/latex]);
  2. Паук находится на одной из стенок ([latex]X_2 = 0[/latex], или [latex]X_2 = A[/latex], или [latex]Y_2 = 0[/latex], или [latex]Y_2 = B[/latex] и [latex]Z_2 \neq 0[/latex]) либо на потолке ([latex]X_2 \neq 0[/latex], и [latex]X_2 \neq A[/latex], и [latex]Y_2 \neq 0[/latex], и [latex]Y_2 \neq B[/latex], и [latex]Z_2 = C[/latex]).

Первый случай тривиален и вычисляется по формуле [latex]\sqrt{(X_1 — X_2)^2 + (Y_1 — Y_2)^2}[/latex].
В случае, когда паук сидит на стенке, мы можем построить 3 развертки:
Допустим, паук находится на левой боковой стенке ([latex]X_2 = 0[/latex]). Остальные случаи аналогичны этому.

  • Паук ползет по этой стенке, затем по полу. Тогда развертка будет такой:
    deploy1
  • Паук ползет через ближнюю к нам стенку и по полу. Тогда развертка следующая:
    deploy2
  • Аналогичен предыдущему случаю, только через дальнюю от нас стенку.

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

  • Паук спускается с потолка на паутине, затем ползет точно так же, как и в самом первом случае.
  • Паук ползет по потолку, по одной из стенок и по полу. Тогда развертка будет выглядеть следующим образом (потолок можно развернуть в 4 стороны — отсюда 4 случая):
    deploy3
  • Паук ползет по потолку, а затем по двум соседним стенкам и по полу. Таких случаев 8, поскольку порядок следования стенок, по которым тот ползет, также важен. Развертка одного из них:
    deploy4

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

Ссылки

Условие задачи на e-olymp
Задача Дьюдени о пауке и мухе
Код решения

e-olymp 130. Прямоугольник

Задача

Заданы координаты трёх вершин прямоугольника. Найдите координаты четвертой вершины.

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

В единственной строке записано шесть чисел — координаты трёх точек.

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

Два числа, координаты искомой вершины прямоугольника. Все входные и выходные данные — целые числа, не превышающие по модулю [latex]100[/latex].

Тесты

Входные данные Выходные данные
[latex]0[/latex] [latex]0[/latex] [latex]0[/latex] [latex]1[/latex] [latex]2[/latex] [latex]1[/latex] [latex]2[/latex] [latex]0[/latex]
[latex]1\, 4\, 4\, 0\, 0\, 2[/latex] [latex]5\, 2[/latex]
[latex]-100[/latex] [latex]-100[/latex] [latex]100[/latex] [latex]100[/latex] [latex]100[/latex] [latex]-100[/latex] [latex]-100[/latex] [latex]100[/latex]
[latex]2[/latex] [latex]-1[/latex] [latex]3[/latex] [latex]1[/latex] [latex]-2[/latex] [latex]1[/latex] [latex]-1[/latex] [latex]3[/latex]
[latex]8\, 0\, 1\, 6\, 0\, 4[/latex] [latex]9\, 2[/latex]

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

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

Прямоугольник

Прямоугольник

Координаты четвертой вершины будут равны сумме координат прилежащих вершин минус координаты противоположной вершины, т. е: [latex]x_4=x_1+x_3-x_2[/latex] и [latex]y_4=y_1+y_3-y_2[/latex]. Но мы не знаем какая из входных вершин противоположна четвертой, а какие — прилежащие. Так как наша фигура это прямоугольник, то противоположная вершина будет при угле [latex]90^{\circ}[/latex]. Произведение перпендикулярных векторов дает [latex]0[/latex]. Перебрав три варианта произведения векторов, заданных входными вершинами, находим вершину при угле [latex]90^{\circ}[/latex]. Остальные две, соответственно, будут прилежащими. Находим координаты четвертой вершины по формуле, заданной выше.

Ссылки

Условие задачи на e-olymp
Код решения