e-olymp 12. Поврежденная картина

Задача

Римская цифра [latex]I[/latex], стоявшая на полу комнаты в точке с координатами [latex]X_0[/latex], [latex]Y_0[/latex], [latex]0[/latex] не выдержала отношения к решению задачи «Римские цифры» и упала на пол. Поскольку нижний конец был прикреплен шарнирно, то он остался на месте, а верхний оказался в точке с координатами [latex]X_1[/latex], [latex]Y_1[/latex], [latex]0[/latex]. В комнате стояла строго вертикально бумажная картина. Зная координаты концов нижнего основания [latex]X_2[/latex], [latex]Y_2[/latex], [latex]0[/latex] и [latex]X_3[/latex], [latex]Y_3[/latex], [latex]0[/latex] и высоту картины [latex]H[/latex] найти длину «разрыва бумаги» на картине.

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

Во входной строке записано 9 чисел [latex]X_0, Y_0, X_1, Y_1, X_2, Y_2, X_3, Y_3, H[/latex]. Все входные данные — целые числа, модуль которых не превышает [latex]10^9[/latex].

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

Программа выводит единственное число – искомую величину с точностью до [latex]0.001[/latex].

Тесты

Входные данные Выходные данные
1 1 6 1 4 0 4 5 6 4.000
0 0 6 0 2 0 5 0 5 2.397
2 0 5 0 0 0 6 0 5 4.172
0 0 5 0 2 0 6 0 1 2.058
0 0 10 0 2 0 6 0 1 0.000

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

Эта задача интересна тем, что для ее решения необходимо смоделировать большое количество разнообразных взаиморасположений картины и буквы. Далее  будут использоваться следующие обозначения: [latex]X_0[/latex]- основание буквы, [latex]X_1[/latex] — ее вершины, [latex]X_2[/latex] и [latex]X_3[/latex] — координаты основания картины, [latex]Н[/latex] — высота картины.

1. [latex]X_0 X_1[/latex] и [latex]X_2 X_3[/latex] лежат на одной прямой

1.1. [latex]X_0[/latex] принадлежит [latex]X_2[/latex][latex]X_3[/latex]

1.1.1. [latex]X_1[/latex]принадлежит [latex]X_2[/latex][latex]X_3[/latex]

1.1.1.1 [latex]X_0[/latex][latex]X_1[/latex] не превышает [latex]Н[/latex]

В таком случае искомая величина — дуга [latex]O X1[/latex], равная [latex]\frac{1}{4} [/latex] длины окружности с радиусом, равным высоте буквы: [latex]O[/latex][latex]X_1[/latex] = [latex]\frac{П\times X_0 X_1}{2} [/latex]

 

1.1.1.2 [latex]X_0[/latex][latex]X_1[/latex] больше, чем [latex]Н[/latex]

в таком случае нам необходимо найти дугу [latex]PB[/latex],для этого умножив радиус на величину центрального угла: [latex]PB[/latex] =[latex]X_0 X_1 \times arcsin \frac{X_0 X_1}{H}[/latex]

1.1.2 [latex]X_1[/latex] не принадлежит [latex]X_2 X_3[/latex]

1.1.2.1 [latex]X_2[/latex] принадлежит [latex]X_0 X_1[/latex]

1.1.2.1.1 [latex]X_0 X_1[/latex] не превышает [latex]H[/latex]

В таком случае нам нужно найти дугу [latex]OM[/latex] по схожему с случаем 1.1.1.2 алгоритму: [latex]OM[/latex] = [latex]X_0 X_1 \times arcsin \frac{X_0 X_2} {X_0 X_1} [/latex]

 

1.1.2.1.2 [latex]X_0[/latex][latex]X_1[/latex] больше [latex]H[/latex]

В таком случае искомая величина равна дуге1 [latex]MN[/latex]= [latex]X_0 X_1 \times  arcsin \frac{H}{X_0 X_1} — arccos \frac{X_0 X_2}  {X_0 X_1}[/latex])

1.1.2 [latex]X_3[/latex] принадлежит [latex]X_0 X_1[/latex]

Данный случай аналогичен предыдущему. Единственное отличие заключается в том, что в формулах необходимо заменить [latex]X_0[/latex][latex]X_2[/latex] на [latex]X_0[/latex][latex]X_3[/latex]

1.2 [latex]Х_1[/latex] принадлежит [latex]X_2[/latex][latex]X_3[/latex]

введем новую переменную [latex]A[/latex], равную расстоянию от [latex]X_0[/latex] до картины.

1.2.1 [latex]X_0 X_1[/latex] меньше, чем [latex]\sqrt{A^2 + H^2}[/latex]

В данном случае нам нужно найти дугу [latex]M X_1[/latex] = [latex]X_0 X_1 \times arccos \frac{A}{X_0 X_1}[/latex]

1.2.2 [latex]X_0[/latex][latex]X_1[/latex] не меньше, чем [latex]\sqrt{A^2 + H^2}[/latex]

в этом случае нам нужно найти дугу [latex]МХ_1[/latex]= [latex]X_0 X_1 \times arсsin \frac{A}{X_0 X_1}[/latex]

 

1.3 обе вершины цифры не принадлежат картине

Обозначим через [latex]A[/latex] расстояние от [latex]X_0[/latex] до дальней вершины картины.

1.3.1 [latex]X_0 X_1 < \sqrt{A^2 + H^2} [/latex]

Искомая величина — дуга [latex]MN[/latex] = [latex]X_0 X_1\times  arcsin \frac{H}{X_0 X_1}  —  arccos \frac{A}{X_0 X_1}[/latex]

2. [latex]X_0 X_1[/latex] и [latex]X_2 X_3[/latex] не лежат на одной прямой

2.1. [latex]X_0 X_1[/latex] пересекает [latex]X_2 X_3[/latex]

В этом случае длина разрыва будет равна длине отрезка [latex]MN[/latex] либо высоте картины, если она окажется меньше вышеупомянутого отрезка.

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

Ссылки

Условие задачи на сайте e-olymp
код к задаче

e-olymp 143. Точка и треугольник

Точка и треугольник

Принадлежит ли точка [latex]O[/latex] треугольнику [latex]ABC[/latex]?

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

Содержит координаты точек [latex]O, A, B, C[/latex]. Числовые значения не превышают по модулю 100.

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

Вывести 1, если точка [latex]O[/latex] принадлежит треугольнику [latex]ABC[/latex] и 0 в противоположном случае.

Входные данные Выходные данные
1 2 6 -9 3 8 1 5 11 1
2 -13 10 -12 5 99 80 17 13 0
3 98 -50 -87 7 5 3 23 17 0
4 5 15 7 12 5 3 2 54 1
5 2 2 3 1 1 3 9 11 1

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

Решение

Для того, чтобы точка [latex]M[/latex] принадлежала треугольнику, заданному точками [latex]D([/latex]$x_{1}$,$y_{1}$[latex]), [/latex] [latex]E([/latex]$x_{2}$,$y_{2}$[latex]), [/latex][latex]F([/latex]$x_{3}$,$y_{3}$[latex]), [/latex] необходимо, чтобы псевдоскалярное (косое) произведение соответствующих векторов было больше либо равно нулю или же меньше либо равно нуля. Пользуясь формулой для косого произведения, запишем произведения векторов.
[$\overline{DE}$,$\overline{MD}$]=($x_{1}$-$x_{0}$) $\cdot$ ($y_{2}$-$y_{1}$)-($x_{2}$-$x_{1}$) $\cdot$ ($y_{1}$-$y_{0}$)
[$\overline{EF}$,$\overline{ME}$]=($x_{2}$-$x_{0}$) $\cdot$ ($y_{3}$-$y_{2}$)-($x_{3}$-$x_{2}$) $\cdot$ ($y_{2}$-$y_{0}$)
[$\overline{FD}$,$\overline{MF}$]=($x_{3}$-$x_{0}$) $\cdot$ ($y_{1}$-$y_{3}$)-($x_{1}$-$x_{3}$) $\cdot$ ($y_{3}$-$y_{0}$)
Если [$\overline{DE}$,$\overline{MD}$], [$\overline{EF}$,$\overline{ME}$] и [$\overline{FD}$,$\overline{MF}$] больше либо равно нулю или же меньше либо равно нуля, то точка принадлежит треугольнику.

 

Ссылки

Ссылка на Ideone
Ссылка на e-olymp

e-olymp 7944. Площадь прямоугольника

Площадь прямоугольника

Найдите площадь прямоугольника.

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

Целочисленные стороны прямоугольника [latex]a[/latex] и [latex]b[/latex]  [latex](1 ≤ a, b ≤ 1000)[/latex].

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

Выведите площадь прямоугольника.

Тесты

# ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
1 [latex]1[/latex] [latex]1[/latex] [latex]1[/latex]
2 [latex]2[/latex] [latex]4[/latex] [latex]8[/latex]
3 [latex]511[/latex] [latex]428[/latex] [latex]218708[/latex]
4 [latex]5555[/latex] [latex]4444[/latex] [latex]24686420[/latex]
5 [latex]11[/latex] [latex]11[/latex] [latex]121[/latex]

 

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

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

Прямоугольником называется четырехугольник, у которого все углы равны. Все углы в прямоугольнике прямые, т.е. составляют [latex]90°[/latex]. Площадь прямоугольника равна произведению его сторон [latex](a, b)[/latex]. Следовательно формула решения задачи будет такой: [latex]a · b[/latex].

Ссылки

• Задача на e-olymp.

• Решение на сайте ideone.

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

e-olymp 932. Высота треугольника

Задача

Определить высоту треугольника площадью [latex]S[/latex], если его основание больше высоты на величину [latex]a[/latex].

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

Два целых числа: [latex]S (0 < S ≤ 100), и[/latex] [latex]a[/latex] ([latex]\left | a \right |[/latex] ≤ 100).

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

Искомая высота с точностью до сотых.

Тесты

# Входные данные Выходные данные
1 20 7 3.73
2 35 3 7.00
3 12 4 3.29
4 67 9 7.92
5 135 13 11.17

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

Алгоритм решения задачи

  1. Формула для вычисления площади треугольника [latex]S=[/latex][latex]\frac{1}{2}\cdot h \cdot c[/latex], где [latex]h[/latex] – высота, а [latex]c[/latex] – сторона, к которой высота проведена.
  2. В задаче сказано, что основание больше высоты на величину [latex]a[/latex]. Значит вместо [latex]c[/latex] мы можем подставить в формулу [latex]h+a[/latex]. Теперь формула приобретает следующий вид: [latex]S=[/latex][latex]\frac{1}{2}\cdot h \cdot \left (h+a \right )[/latex]
  3. Cовершив некоторые преобразования приходим к квадратному уравнению [latex]h^{2}+a\cdot h-2\cdot S = 0[/latex]
  4. Далее находим дискриминант по формуле [latex]D = a^{2}+4\cdot2\cdot S[/latex]. Находим корень квадратный из дискриминанта [latex]\sqrt{D}[/latex]
  5. Находим высоту по формуле [latex]h=\frac{-a+\sqrt{D}}{2}[/latex]
  6. Второй корень нам не подходит, потому что он меньше [latex]0[/latex], а длина не может быть отрицательной.
  7. Подставляем исходные данные в формулы, получаем результат.

Также подробное описание представлено в коде программы.

Ссылки

Ссылка на e-olymp

Ссылка на ideone