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

Latest posts by Алиса Ворохта (see all)

Задача

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

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

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

В первой строке заданы размеры комнаты [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]

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

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

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

Рассмотрим такие случаи:

  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] с помощью функции [latex]distance[/latex].
В случае, когда паук сидит на стенке, мы можем построить 3 развертки:
Допустим, паук находится на левой боковой стенке ([latex]X_2 = 0[/latex]). Остальные случаи аналогичны этому.

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

По этим разверткам мы можем вычислить координаты паука и кратчайшее расстояние от него до мухи с помощью функции [latex]distance[/latex]. Если же паук находится в одном из углов комнаты, то мы находим наименьшее расстояние из двух вариантов развертки.
Когда же паук сидит на потолке, не соприкасаясь ни с одной из стенок, у него есть 13 вариантов:

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

По этим разверткам мы также можем вычислить координаты паука и кратчайшее расстояние от него до мухи с помощью функции [latex]distance[/latex].

Ссылки

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

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
Код решения задачи

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

Костя Григорян
Костя Григорян

Latest posts by Костя Григорян (see all)

Задача

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

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

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

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

Два числа, координаты искомой вершины прямоугольника. Все входные и выходные данные — целые числа, не превышающие по модулю [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
Код решения

e-olimp 57. Бабочка-санитар

Бондаренко Кирилл
Бондаренко Кирилл

Latest posts by Бондаренко Кирилл (see all)

Задача

e-olimp 57. Бабочка-санитар

e-olimp 57. Бабочка-санитар

Школьники, идя из дому в школу или наоборот — со школы домой, любят кушать конфеты. Но, как всегда, это приятное дело иногда имеет неприятные последствия – детки часто выбрасывают обертки на школьном дворе.
Мурзик всегда следил за чистотой школьного двора и ему в этом с радостью помогали бабочки, благодарные за прекрасные фотографии, сделанные им. Бабочки могли использовать собственные крылышки как линзы, причем они могли изменять их фокусное расстояние. Заметив обертку от конфетки, лежавшую на школьном дворе в точке с координатами [latex]X_1[/latex], [latex]Y_1[/latex], бабочка перелетала в точку с координатами [latex]X_2[/latex], [latex]Y_2[/latex], [latex]Z_2[/latex], расположенную на пути солнечных лучей к обертке и, изменяя фокусное расстояние своих крылышек-линз, сжигали обертку от конфеты.
Какую оптическую силу [latex]D[/latex] имели крылышки-линзы бабочки в этот момент? Continue reading

Площадь поверхности

Задача

Найти площадь поверхности, которая является трёхмерным графиком функции [latex]f\left( x, y\right)[/latex], в пределах от [latex]a[/latex] до [latex]b[/latex] по оси [latex]x[/latex] и от [latex]c[/latex] до [latex]d[/latex] по оси [latex]y[/latex] c величиной шага [latex]h[/latex].

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

Четыре целых числа: [latex]a[/latex], [latex]b[/latex], [latex]c[/latex], [latex]d[/latex].
Вещественное число: [latex]h[/latex].

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

Площадь поверхности [latex]S[/latex].

Тесты

 № [latex]f\left( x, y\right)[/latex] Входные данные Выходные данные
 [latex]a[/latex]  [latex]b[/latex]  [latex]c[/latex]  [latex]d[/latex]  [latex]h[/latex]  [latex]S[/latex]
 1  [latex]x+y[/latex]  -10  10  -10  10  0.001  692.82
 2  [latex]\left| x \right| +\left| y \right|[/latex]  -2  2  -2  2  0.005  27.7128
 3  [latex]1[/latex]  0  100  0  100  0.1  10000
 4  [latex]{x}^{2}+{y}^{2}[/latex]  -1  1  -1  1  0.0005  7.44626

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

Решение

Представим поверхность в виде множества геометрических фигур. Тогда её площадь будет суммой площадей этих фигур. В качестве фигур, покрывающих данную поверхность, возьмём треугольники, поскольку через любые [latex]3[/latex] точки в пространстве можно провести плоскость и только одну (а значит и треугольник). Координатную плоскость [latex]xy[/latex] условно поделим на квадраты, где сторона квадрата будет равняться заданному шагу [latex]h[/latex]. Будем рассматривать только квадраты, что лежат в заданных пределах.  Условно проведём одну из диагоналей у каждого квадрата — получим треугольники на плоскости. Поочередно будем искать координату [latex]z[/latex] вершин каждой пары треугольников, подставляя уже известные координаты [latex]x[/latex] и [latex]y[/latex] в указанную формулу. Зная координаты треугольников в пространстве, найдём площадь каждого, сумма данных площадей и будет площадью поверхности. Чтоб найти площадь треугольника, зная координаты его вершин, найдем векторное произведение его координат. Возьмем треугольник с координатами вершин  [latex]\left( x_i,y_i,z_{ii} \right) [/latex], [latex]\left( x_i, y_j, z_{ij} \right) [/latex] и [latex]\left( x_j, y_i, z_{ji} \right) [/latex], возьмём произвольные два вектора, которые образуют данный треугольник — [latex]\overrightarrow { a } =\left ( x_i-x_i, y_j-y_i, z_{ij}-z_{ii} \right)[/latex], [latex]\overrightarrow { b } =\left ( x_j-x_i, y_i-y_i, z_{ji}-z_{ii} \right)[/latex].
[latex]\overrightarrow { a } =\left ( 0, y_j-y_i, z_{ij}-z_{ii} \right)[/latex], [latex]\overrightarrow { b } =\left ( x_j-x_i, 0, z_{ji}-z_{ii} \right)[/latex].
Тогда векторное произведение [latex]\left [ \overrightarrow { a }, \overrightarrow { b } \right] =\left ( (y_i-y_j)( z_{ji}-z_{ii}), (z_{ii}-z_{ij})(z_{ji}-z_{ii} ), ( y_j-y_i)(x_j-x_i) \right)[/latex].
Поскольку длина вектора равного векторному произведения двух векторов в пространстве равна площади параллелограмма, образованного исходными векторами — найдём его длину и разделим пополам, чтоб получить площадь треугольника, образованного исходными векторами. Значит площадь каждого треугольника можно вычислить по формуле:
[latex]s =\frac { 1 }{ 2 } \sqrt{({(y_i-y_j)}^{2}{( z_{ji}-z_{ii})}^{2}+{(z_{ii}-z_{ij})}^{2}{(z_{ji}-z_{ii} )}^{2}+{( y_j-y_i)}^{2}{(x_j-x_i)}^{2})}[/latex] Тогда площадь поверхности в пределах заданных точек можно вычислить, сложив площади этих треугольников.

Модификация

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

Тесты

 № [latex]f\left( x, y\right)[/latex] [latex]z_0[/latex]  Входные данные  Выходные данные
 [latex]a[/latex]  [latex]b[/latex]  [latex]c[/latex] [latex]d[/latex]  [latex]h[/latex]  [latex]S[/latex]
 1 [latex]\sqrt { 1-{ x }^{ 2 }-{ y }^{ 2 } }[/latex] [latex]1[/latex]  -1  1  -1  1  0.00011  6.28734
 2 [latex]\sqrt { 1-{ x }^{ 2 }-{ y }^{ 2 } }[/latex] [latex]7y[/latex]  -1  1  -1  1  0.00011  23.0803
 3 [latex]\sqrt { 1-{ x }^{ 2 }-\frac{ { y }^{ 2 }}{ 2 } }[/latex] [latex]0[/latex]  -1  1  -2  2  0.00015  8.08214
 4 [latex]\sqrt { 2-{ x }^{ 2 }-{ y }^{ 2 } }[/latex] [latex]-1[/latex]  -2  2  -2  2  0.0005  12.5835

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

Условно отделим от функцию [latex]f\left( x, y\right)[/latex] слагаемые, что не под корнем, если такие имеются. Тогда [latex]z_0[/latex] равно части функции, что не под корнем. Для того, чтоб рассматривать площади треугольников, вершины которых выходят за область определения функции, доопределим их в [latex]z_0[/latex] по оси [latex]z[/latex]. Затем вычислим площадь треугольников, у которых как минимум одна вершина не лежит на [latex]z=z_0[/latex] .

Ссылки

Mif 9. Пересечение отрезков

Задача

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

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

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

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

Пересекаются ли отрезки.

Тесты

Входные данные Выходные данные
[latex]x1[/latex] [latex]y1[/latex] [latex]x2[/latex] [latex]y2[/latex] [latex]x3[/latex] [latex]y3[/latex] [latex]x4[/latex] [latex]y4[/latex]
1 0 2 1 1 0 2 0 Отрезки пересекаются
-1 1 2 -2 0 -2 1 3 Отрезки пересекаются
1 1 2 2 2 2 1 1 Отрезки пересекаются
-1 1 -1 2 1 1 2 2 Отрезки не пересекаются
-2 -1 -2 3 0 -1 0 3 Отрезки не пересекаются
-2 0 0 2 0 -2 1 1 Отрезки не пересекаются

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

Решение

Пусть концы отрезков имеют координаты [latex](x1,y1),[/latex] [latex](x2,y2),[/latex] [latex](x3,y3),[/latex] и [latex](x4,y4),[/latex]. По имеющимся точкам выведем параметрические уравнения обоих отрезков: [latex]0\leq u \leq 1:[/latex] $$\begin{cases}x=ux1+(1−u)x2; \newline y=uy1+(1−u)y2\end{cases};$$ и [latex] 0\leq v \leq 1:[/latex] $$\begin{cases}x=vx3+(1−v)x4 \newline y=vy3+(1−v)y4\end{cases}$$
В точке пересечения [latex]x[/latex] и [latex]y[/latex] должны совпадать. Значит выходит система двух линейных уравнений, которую нужно решить относительно [latex]u[/latex] и [latex]v:[/latex] $$\begin{cases}ux1+(1−u)x2=vx3+(1−v)x4 \newline uy1+(1−u)y2=vy3+(1−v)y4\end{cases}$$
Найдем определитель: [latex]denominator=(y4-y3)\cdot(x1-x2)-(x4-x3)\cdot(y1-y2).[/latex] Если он равен [latex]0[/latex], то прямые содержащие отрезки параллельны или совпадают. В этом случае проверим лежит ли вершина одного отрезка на другом, если она лежит, то отрезки пересекаются, иначе не пересекаются.
Если не [latex]0[/latex], то найдем решение по правилу Крамера:
$$\begin{cases}Ua=\frac{(x4-x2)\cdot(y4-y3)-(x4-x3)\cdot(y4-y2)}{denominator} \newline Ub=\frac{(x1−x2)\cdot(y4−y2)−(x4−x2)\cdot(y1−y2)}{denominator}\end{cases}$$
Если [latex]0\leq Ua \leq 1[/latex] и [latex]0\leq Ub \leq 1[/latex], то отрезки пресекаются, иначе отрезки не пересекаются.

Ссылки

Ideone