e-olymp 8649. Емблема (Emblem)

Умова

До проведення $N$-ї ярмарки «Мікротехнології у макропрограмуванні» дизайнери розробили емблему, у якій на квадрат розміром $N \times N$ дм «ставився зверху» квадрат розміром $\left(N-1\right) \times \left(N-1\right)$ дм і так далі. Зверху був квадрат $1 \times 1.$ В цілому організаторам емблема сподобалася, але вони забажали «прикрасити» її золотистою стрічкою, яка йшла б від лівого нижнього кута до правого верхнього, потім по верхньому краю і спускалася до правого нижнього кута (див. малюнок). У найближчому магазині можна було купити стрічку за ціною $Р$ грн. за дм, але відпускалися стрічки тільки з цілою кількістю дм. У той же час магазин пропонував знижку $10\%$, якщо покупка коштувала не менше $100$ грн. і $15\%$ при покупці від $1000$ грн. Скільки щонайменше доведеться заплатити за цю «прикрасу»? Нагадаємо, що на декартовій площині довжина відрізку між точками $\left(x_{1};y_{1}\right)$ та $\left(x_{2};y_{2}\right)$ обчислюється за формулою: $d=\sqrt{\left(\left(x_{2}-x_{1}\right)^{2}+\left(y_{2}-y_{1}\right)^{2} \right)}.$

Вхідні дані:

Програма вводить два натуральних числа $N$ – номер ярмарки та $P$ -ціна стрічки у гривнях за дм $\left(1 \leqslant N \leqslant 100\right).$

Вихідні дані:

Ціна стрічки у копійках (щоб не працювати з дробовими числами).

Тести:

Вхідні дані Вихідні дані
2 13 9360
5 10 28800
100 1 858670
1 5 2000
12 3 42660

Рішення:

Пояснення:  Спочатку необхідно знайти довжину діагоналі, для цього, умовно ми можемо продовжити саму верхню пряму в праву і ліву сторону до того моменту поки її довжина не стане не менш ніж $N$ дм, а потім починаючи з лівого нижнього кута куба $N \times N$ провести перпендикуляр до цієї прямої. Так у нас вийде прямокутний трикутник, в якому h (знаходимо за формулою $n$-перших членів арифметичної прогресії $S_{n} = \frac{a_{1}+a_{n}}{2} \cdot n$) та l — катети, тоді за теоремою Піфагора можемо знайти діагональ d. Далі знаходимо довжину стрічки і її ціну з огляду на знижки. Також необхідно зробити перевірку, чи буде вигідніше придбати стрічку на таку кількість грошей, яке буде відповідати умовам знижки.

e-olymp 1509. Раздел королевства.

Задача


Король страны Геометрии в заботах. У него есть три сына, которые постоянно ссорятся. Король применял разные методы примерения, но все напрасно. И это его очень беспокоило.

«А что если разделить королевство?» подумал король. Он пригласил советников и описал свой план. Король открыл карту.

Королевство имеет форму треугольника с вершинами [latex]A, B, C[/latex]. Король провел линию от [latex]B[/latex] к [latex]E[/latex] ([latex]E[/latex] — произвольная точка на отрезке [latex]AC[/latex]) и линию от [latex]C[/latex] к [latex]F [/latex]([latex]F[/latex] — произвольная точка на отрезке [latex]AB[/latex]). Пересечение [latex]BE[/latex] и [latex]CF[/latex] обозначено через [latex]X[/latex].

Теперь образовалось четыре части — [latex]a[/latex] (треугольник [latex]BFX[/latex]), [latex]b[/latex] (треугольник [latex]BCX[/latex]), [latex]c[/latex] (треугольник [latex]CEX[/latex]) и [latex]d[/latex] (четырехугольник [latex]AEXF[/latex]). Король решил отдать области[latex] a[/latex], [latex]b[/latex], [latex]c[/latex] трем сыновьям. А область [latex]d[/latex] станет новым королевством.

Вы — главный советник. Король сообщает Вам значения [latex]a, b, c[/latex]. Вам необходимо найти значение [latex]d[/latex]. Если его найти невозможно, то сообщить об этом.

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

Состоит из не более чем [latex]1000[/latex] тестов. Каждый тест содержит три неотрицательных действительных числа [latex]a[/latex], [latex]b[/latex], [latex]c[/latex] (разделенных пробелом). Входные данные заканчиваются тестом у которого [latex]a = -1[/latex] и он не обрабатывается.

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

Для каждого теста вывести его номер, начиная с [latex]1[/latex]. В следующей строке вывести [latex]d[/latex] (величина области королевства после раздела) округленное до [latex]4[/latex] десятичных знаков или ‘Poor King!’ (без кавычек) если значение [latex]d[/latex] определить невозможно. Формат выходных данных показан в примере.

Тесты

Входные данные Выходные данные
1 1 2 1 Set 1:
2.0000
2 2 4 2 Set 2:
4.0000
3 1 3 3 Set 3:
5.0000
4 -1 0 0

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


 

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


Для решения задачи соединим точки  [latex]F[/latex] и [latex]E[/latex] линией. Получили два треугольника: [latex]d1[/latex] и [latex]d2[/latex]. Искомую площадь [latex]d[/latex] будем искать как сумму площадей [latex]d1[/latex] и [latex]d2[/latex]. Треугольники [latex]BFO[/latex] и [latex]EFO[/latex] имеют общее основание [latex]FO[/latex]. Следовательно их площади [latex]d1[/latex] и [latex]a[/latex] относятся как высоты, опущенные из вершин [latex]E[/latex] и [latex]B[/latex] на прямую [latex]FO[/latex]. Аналогично треугольники [latex]BCO[/latex] и [latex]ECO[/latex] имеют общее основание [latex]OF[/latex]. Значит их площади [latex]c[/latex] и [latex]b[/latex] относятся как высоты, опущенные из вершин [latex]E[/latex] и [latex]B[/latex] на прямую [latex]CO[/latex]. То есть $\frac{d_1}{a}=\frac{c}{b}$. Отсюда $d_1=\frac{ac}{b}$. Теперь рассмотрим треугольники [latex]CAF[/latex] и [latex]CBF[/latex] с основаниями [latex]AF[/latex] и [latex]BF[/latex]. Они имеют одинаковую высоту, опущенную из вершины [latex]С[/latex] на прямую [latex]AB[/latex]. Следовательно площади этих треугольников относятся как длины сторон [latex]AF[/latex] и [latex]BF[/latex]. Аналогично треугольники [latex]EAF[/latex] и [latex]EBF[/latex] имеют основания [latex]AF[/latex] и [latex]BF[/latex]. Они имеют одинаковую высоту, опущенную из вершины [latex]E[/latex] на прямую [latex]AB[/latex]. Площади этих треугольников относятся как длины сторон [latex]AF[/latex] и [latex]BF[/latex]. Тогда $$\frac{AF}{BF}=\frac{S_{\blacktriangle} CAF}{S\blacktriangle CBF}=\frac{c+d_1+d_2}{a+b}$$. $$\frac{AF}{BF}=\frac{S\blacktriangle EAF}{S\blacktriangle EBF}=\frac{d_2}{a+d_1}$$. Следовательно $\frac{c+d_1+d_2}{a+b}=\frac{d_2}{a+d_1}$. Поскольку [latex]d1[/latex] уже найдено, то имеем равенство с одним неизвестным [latex]d2[/latex] : $$d_2=\frac{(c+d_1)(a+d_1)}{b-d_1}$$. Если [latex]b \leqslant d1[/latex], то решения не существует.

Ссылки

  • Условие задачи на e-olymp
  • Код программы на ideone

Proggy-Buggy 2018: Задача E. Треугольник или не треугольник?

Задача

Баги считает треугольником любые три различные точки плоскости, соединенные отрезками. Даже написал диссертацию: «Треугольник или не треугольник? Вот в чём вопрос!», которая породила множество вопросов. Его очень утомили вопросы из разряда, «а это треугольник?». Если хотите, помогите Баги: напишите программу «Баги-бот», которая вместо Баги отвечала бы на вопрос, образуют ли три заданные точки треугольник.

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

Строка содержащая три пары целых чисел, координаты $x1$, $y1$, $x2$, $y2$, $x3$, $y3$ $(0\leq xi,yi\leq1000)$, разделенных пробелом.

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

Строка «$yes$» или «$no$» (без кавычек) — ответ программы «Баги-бот».

Тесты

# ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
1 0 0 1 0 0 1 $yes$
2 1 1 1 2 1 3 $yes$
3 1 1 1 1 1 2 $no$

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

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

В задаче главное внимательно прочитать условие. Если любые две заданные точки совпадают, то программа «Баги-бот» должна ответить no, иначе yes.

Ссылки

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

e-olymp 8372. Составить треугольник

Задача взята с сайта e-olymp

Задача

По заданным длинам трех отрезков определить, можно ли из них составить невырожденный треугольник. Треугольник называется невырожденным, если его площадь больше 0.

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

Три натуральных числа $a, b, c (1 ≤ a, b, c ≤ 1000)$ — длины трех отрезков.

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

Вывести YES если из отрезков можно составить невырожденный треугольник и NO в противном случае.

Тесты

# ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
1 5 6 7 YES
2 3 7 4 NO
3 16 24 32 YES
4 54 1 100 NO
5 1 1 1 YES

Код программы (Ветвление)

Код программы (Линейные вычисления)

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

Пусть $a, b, c$ – длины трех отрезков. Из них можно составить невырожденный треугольник, если длина каждых двух отрезков больше длины третьего (это условие известно как неравенство треугольника): | $b$ | < | $a$ | + | $c$ | \begin{cases} b + c > a\\a + c > b\\a + b > c\end{cases}

Ссылки

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

Код программы на ideone (Линейные вычисления)

Код программы на ideone (Ветвление)

e-olymp 47. Паркет из треугольников

Задача

Прямоугольную комнату размерами [latex]m[/latex] на [latex]n[/latex] (сначала по горизонтали, а потом по вертикали) замостили треугольными плитками и их пронумеровали, как показано на рисунке.

За один шаг можно переместиться с одной паркетины на другую только через общую сторону. Найти наименьшее количество шагов, нужных для перемещения с паркетины [latex]a[/latex] на паркетину [latex]b[/latex].

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

Во входном файле в первой строке через пробел заданы значения [latex]n[/latex], [latex]m[/latex] [latex](1 ≤ n, m ≤ 100)[/latex], а во второй — [latex]a[/latex], [latex]b[/latex].

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

Искомое количество шагов.

Тесты

# Входные данные Выходные данные
1 5 4
25 38
5
2 5 4
6 22
4
3 5 4
15 22
3
4 3 2
1 12
7
5 3 2
6 12
2

Код 1

Код 2

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

Способ 1

Каждый элемент имеет три параметра:

  1. Положение в строке
  2. Положение в столбце
  3. Четность

Для хранения этих значений создадим трёхмерный массив. Существует несколько вариантов расположения элементов в нем:

  1. Оба элемента расположены в одной строке строке
  2. Оба элемента расположены в одном столбце
  3. Оба элемента расположены на одной диагонали
  4. Произвольное расположение

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

Позиция [latex]7[/latex] [latex]\left[ 0 , 3 , 0 \right] [/latex].
Позиция [latex]14[/latex] [latex]\left[ 1 , 2 , 1 \right] [/latex].
Для случая [latex] 5*4 [/latex] эти элементы расположены на одной диагонали. Далее идет создание вспомогательного 3-х мерного массива, в который мы положим координаты [latex]7[/latex]. Идея состоит в том, чтобы временный массив и массив с координатам [latex]14[/latex] совпали. Т.к [latex]7[/latex] нечетное, а [latex]14[/latex] четное, то первый «шаг» будет сделан по горизонтали, тем самым мы уровняем координату, отвечающую за четность. Далее идет сравнение по «строчной» координате, т.к. они не совпадают, то делается «шаг» вниз. Далее остается сделать «шаг» влево, чтобы совпали координаты по столбцам.
Аналогичные проверки делаются для остальных случаев.
Важно отметить, что лучше всего для проверки подходят переменные типа bool. Поэтому в некоторых местах были использованы преобразование из типа int в тип bool. Делалось это при помощи следующей строки кода

Для более оптимальной работы были использованы тернарные операции. Они скрывают под собой условие, выполнение которого состоит из одной строки кода.

Способ 2

Для того, чтобы наш код был универсален для случая [latex]firstNumber > lastNumber[/latex] и [latex]firstNumber < lastNumber[/latex] мы меняем местами [latex]firstNumber[/latex] и [latex]lastNumber[/latex].
Следующим шагом будет определение позиции [latex]firstNumber[/latex] и [latex]lastNumber[/latex]. Положим, что [latex] x [/latex] — это позиция в строке, а [latex] y [/latex] — столбце. Удобнее всего хранить значения в массиве, поэтому мы создаем

массив, переменные в котором будет иметь тип [latex] int [/latex], а размер будет фиксированный. Для определения количества шагов заведем переменную с типом [latex] int [/latex].
Важно отметить, что идея решения данного способа состоит в том, чтобы на позиции

стояло количество шагов, совершенных в ходе решения.

Ссылки

Задача на e-olymp

Код задачи на ideone ( способ 1 )

Код задачи на ideone ( способ 2 )

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

ML29. Площадь тетраэдра

Тетраэдр

Тетраэдр

Задача. Найти площадь полной поверхности тетраэдра три стороны которого образованы векторами [latex]\overrightarrow{a}=(a_x,a_y,a_z)[/latex], [latex] \overrightarrow{b}=(b_x,b_y,b_z)[/latex] и [latex]\overrightarrow{c}=(c_x,c_y,c_z)[/latex].
Тесты:

Вход Выход
[latex]a_x[/latex] [latex]a_y[/latex] [latex]a_z[/latex] [latex]b_x[/latex] [latex]b_y[/latex] [latex]b_z[/latex] [latex]c_x[/latex] [latex]c_y[/latex] [latex]c_z[/latex] [latex]S[/latex]
1 -3 3 3 3 -3 3 3 3 -3 69.3607
2 -1 1 1 1 -1 1 1 1 -1 7.70674
3 -2 2 2 2 -2 2 2 2 -2 30.827
4 0 0 1 1 0 0 1 1 -1 2.07313

Код на C++:

Код на Java:

Решение:
Координаты векторов находим по формуле:
[latex] \overrightarrow{A_2A_4}=(c_x-a_x,c_y-a_y,c_z-a_z) [/latex]
здесь [latex] a_x, a_y, a_z[/latex] — координаты точки [latex]A_2[/latex]; [latex]c_x, c_y, c_z[/latex] — координаты точки [latex]A_4[/latex];
Таким же образом находим остальные координаты векторов.
Модули векторов (длина ребер пирамиды)
Длина вектора [latex]\overrightarrow{a}(a_x;a_y;a_z)[/latex] выражается через его координаты формулой:
[latex] \left| \overrightarrow{A_1A_2} \right| =\sqrt { ({ a_x) }^{ 2 }+({ a_y) }^{ 2 }+({ a_z) }^{ 2 } } [/latex];
Таким же способом находим другие модули векторов.
Площадь грани можно найти по формуле:
[latex] s_1=\frac { 1 }{ 2 } \vec{A_1} \times \vec{A_2} \sin \angle{A_2A_3} [/latex]
где
[latex] \sin \angle{ A_2A_3 =\sqrt { 1-{ (\cos \angle{ A_2A_3) } }^{ 2 } } } [/latex]
Так же будем находить и другие.
Найдем угол между ребрами [latex] A_1A_2(a_x;a_y;a_z) [/latex] и [latex] A_1A_3(b_x;b_y;b_z) [/latex]:
[latex] \cos \angle{ A_2A_3 =\frac { a_x b_x+a_y b_y+a_z b_z }{ \left| A_2A_3 \right| } } [/latex]
Так мы найдём и другие 3 площади граней.
Площадь полной поверхности.
[latex] s=s_1+s_2+s_3+s_4. [/latex]

Ссылки:

Онлайн компилятор ideone C++ .
Онлайн компилятор ideone Java .
Онлайн калькулятор .

ML38. Максимальный размер прямоугольника, вырезанного из круга

Задача. Какого наибольшего размера прямоугольник можно вырезать из круга диаметра [latex]d[/latex], если известно, что длины его сторон образуют золотую пропорцию.

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

Единственное число — диаметр окружности.

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

Два числа — длины сторон прямоугольника.

ml38

Тесты.

Входные данные Выходные данные
[latex]d[/latex] [latex]a[/latex] [latex]b[/latex]
1 0 0 0
2 1 0.850651 0.525731
3 2 1.7013 1.05146
4 21 17.8638 11.0404
5 0.32 0.272208 0.168234
6 1.7 1.44611 0.893743
7 134 113.981 70.448

Код программы на C++.

Код программы на Java.

Решение.

Прямоугольник будет иметь наибольший размер в случае, когда его вершины лежат на окружности. Тогда, очевидно, диаметр окружности будет диагональю данного прямоугольника. Согласно условию, длины его сторон образуют золотую пропорцию. Это означает, что [latex]\frac { a }{ b } =\phi [/latex], где [latex]a[/latex] — длина большей стороны прямоугольника, [latex]b[/latex] — длина его меньшей стороны, а [latex]\phi=\frac { 1+\sqrt { 5 } }{ 2 } [/latex]. Отсюда [latex]a=b\cdot \phi[/latex]. По теореме Пифагора, [latex]{ a }^{ 2 }+{ b }^{ 2 }={ d }^{ 2 }[/latex]. Путём подстановки из предыдущего выражения и простых алгебраических преобразований получим формулу для вычисления длины меньшей стороны: [latex]b=d\cdot \sqrt { \frac { 1 }{ { \phi }^{ 2 }+1 } } [/latex].
Сначала для удобства находим значение [latex]\phi[/latex], затем — по указанным формулам длины сторон прямоугольника.

Ссылка на код на ideone.com: здесь (C++) и здесь (Java).

ML26. Площадь треугольника

Задача.

Найти площадь треугольника по заданным координатам его вершин [latex] A(x_a,y_a,z_a )[/latex], [latex]B(x_b,y_b,z_b)[/latex] и [latex]C(x_c,y_c,z_c)[/latex].

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

Координаты вершин треугольника [latex]ABC[/latex]

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

Площадь [latex]S[/latex] треугольника [latex]ABC[/latex]

Тесты

Входные данные Выходные данные
[latex]x_a [/latex] [latex]y_a [/latex] [latex]z_a [/latex] [latex]x_b [/latex] [latex]y_b [/latex] [latex]z_b [/latex] [latex]x_c [/latex] [latex]y_c [/latex] [latex]z_c [/latex] [latex]S [/latex]
-2 1 2 3 -3 4 1 0 9 19.7864
-3 13 -5 6 11 12 4 8 18 50.5618
-6 0 4 5 1 3 -3 -1 -4 43.307
-6 -2.3 -8.2 1.9 -7.8 0.2 -8.5 3.4 -8.9 28.0909

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

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

Используя известные нам координаты вершин треугольника и формулу вычисления расстояния между двумя точками в пространстве [latex]AB=\sqrt{(x_2-x_1)^2+(y_2-y_1)^2+(z_2-z_1)^2}[/latex]
можно найти длины сторон треугольника [latex]ABC[/latex]. Для нахождения площади используем Формулу Герона[latex]AB=\sqrt{p*(p-a)*(p-b)*(p-c)}[/latex] перед этим находим полупериметр [latex]p[/latex] по формуле [latex]p=\frac{a+b+c}{2}[/latex] подставляем значение и выводим конечный результат.

Ссылки

Условие задачи.
ideone

Mif 17.13

17_13

Задача №17.13

Условие

Принадлежит ли точка (х;у) фигуре на рисунке? Варианты 1-20. Пожалуйста повторите в своём отчёте рисунок, выполнив его в формате SVG.

Тесты

Входные данные (точка K) Выходные данные
(3;4) no
(1;1) yes
(1;4) yes
(3;0) yes
(0;6) no
(-13; -3) no
(-4.5; -3) yes

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

Для запроса на выполнение нажать здесь.

Решение

[latex](x — x_A)(y_B — y_A) — (y — y_A)(x_B — x_A) = 0[/latex] — уравнение прямой, проходящей через точки [latex]A[/latex] и [latex]B[/latex]. Тогда для любой точки [latex](x; y)[/latex] можно определить её местоположение относительно прямой [latex]AB[/latex]. Если левая часть неравенства будет равно 0, то точка лежит на прямой. Прямая [latex]AB[/latex] разбивает плоскость на две полуплоскости. Точки лежащие в одной полуплоскости будут давать положительные значения, а точки из другой полуплоскости — отрицательные. Тогда, объединением условий местоположения точки [latex](x; y)[/latex] и местоположения точек [latex]C, A, B[/latex] относительно прямых [latex]AB[/latex], [latex]BC[/latex], [latex]AC[/latex] соответственно, мы сможем определить местоположение данной точки относительно треугольника.

По рисунку видно, что [latex]A(1;4), B(5, -4), C(-5, -3)[/latex]. Тогда, определяем положение точки [latex]K[/latex] относительно каждой прямой и точки не лежащей на данной прямой треугольника [latex]ABC[/latex].

 

Mif 7. Тип треугольника

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

Постановка задачи

Даны действительные числа [latex]x[/latex], [latex]y[/latex], [latex]z[/latex], задающие длины сторон некоторого треугольника. Будет ли треугольник остроугольным, тупоугольным или прямоугольным? Какой из трёх случаев самый маловероятный?

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

По теореме косинусов
[latex]a^2 = b^2 + c^2 — 2 \cdot b \cdot c \cdot \cos\alpha[/latex],
где [latex]a[/latex], [latex]b[/latex], [latex]c[/latex] — стороны треугольника, а [latex]\alpha[/latex] — угол между [latex]a[/latex] и [latex]b[/latex], тогда
[latex]\alpha = \arccos\frac{b^2 + c^2 — a^2}{2 \cdot b \cdot c}[/latex],
[latex]\beta = \arccos\frac{c^2 + a^2 — b^2}{2 \cdot a \cdot c}[/latex],
[latex]\gamma = \arccos\frac{a^2 + b^2 — c^2}{2 \cdot a \cdot b}[/latex],
где [latex]\alpha[/latex], [latex]\beta[/latex], [latex]\gamma[/latex] — углы треугольника.
Если самый большой угол больше [latex]\frac{\pi}{2}[/latex], то треугольник тупоугольный, если самый большой угол равен [latex]\frac{\pi}{2}[/latex], то треугольник прямоугольный, если самый большой угол меньше [latex]\frac{\pi}{2}[/latex], то треугольник остроугольный. Так как треугольник является прямоугольным только в том случае, когда самый большой угол равен [latex]\frac{\pi}{2}[/latex], этот случай является самым маловероятным.

Тесты

Входные данные Выходные данные
[latex]a[/latex] [latex]b[/latex] [latex]c[/latex]
2 2 3 Тупоугольный
3 4 5 Прямоугольный
1 1 1 Остроугольный

Реализация

ideone: ссылка

Mif 17.15

Задача Mif17.15

Условие задачи

Принадлежит ли точка [latex](x, y)[/latex] фигуре на рисунке?

Viktoriya_Kudymovskaya (1)

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

В одной строке задано два числа – координаты точки latex[/latex].

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

Вывести: «Принадлежит» или «Не принадлежит»(без кавычек).

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

Тестирование

Входные данные Выходные данные
1. 1.5 7 Не принадлежит
2. 3 4 Не принадлежит
3. 2 -3.6 Принадлежит
4. 5 0 Принадлежит
5. 0 1 Не принадлежит
6. 0 -4 Не принадлежит
7. 3 3 Принадлежит
8. 2 3 Принадлежит

Реализация

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

Пусть на плоскости дан треугольник [latex]ABC[/latex] с такими координатами вершин: [latex]A(x_1, y_1)[/latex], [latex]B(x_2, y_2)[/latex] и [latex]C(x_3, y_3)[/latex]. А  [latex]D(x, y)[/latex] — произвольная точка на координатной плоскости. Положим, [latex]A(x_1, y_1)[/latex], [latex]B(x_2, y_2)[/latex], [latex]C(x_3, y_3)[/latex] и [latex]D(x, y)[/latex] — векторы.

  1. Для того, чтобы точка [latex]D(x, y)[/latex] принадлежала данному треугольнику, необходимо, чтобы псевдоскалярное (косое) произведение соответствующих векторов было больше или же меньше нуля.
  2. Если векторы заданы своими координатами [latex]a(x_1, y_1), b(x_2, y_2)[/latex], то их косое произведение [latex][a,b]=x_1\cdot y_2 — x_2\cdot y_1[/latex]. Пользуясь данной формулой, запишем косое произведение векторов [latex]A(x_1, y_1)[/latex], [latex]B(x_2, y_2)[/latex] и [latex]D(x, y)[/latex]: [latex]k=x_1y_2 — x_2y_1 — x_1y + xy_1 + x_2y — xy_2=(x_1 — x)\cdot (y_2 — y_1) — (x_2 — x_1)\cdot (y_1 — y)[/latex].
  3. Далее запишем косое произведение векторов [latex]B(x_2, y_2)[/latex], [latex]C(x_3, y_3)[/latex] и [latex]D(x, y)[/latex]: [latex]m=x_2y_3 — x_3y_2 — x_2y + xy_2 + x_3y — xy_3=(x_2 -x)\cdot (y_ 3- y_2) — (x_3 — x_2)\cdot (y_2 — y)[/latex].
  4. Запишем косое произведение векторов [latex]A(x_1, y_1)[/latex], [latex]C(x_3, y_3)[/latex] и [latex]D(x, y)[/latex] : [latex]n=x_1y_3 — x_3y_1 — x_1y + xy_1 + x_3y — xy_3=(x_3 — x)\cdot (y_1 — y_3) — (x_1 — x_3)\cdot (y_3 — y)[/latex].
  5. Если [latex]k \leq 0 [/latex] и [latex]m \leq 0[/latex] и [latex]n \leq 0[/latex]  или [latex]k \geq 0[/latex] и [latex]m \geq 0[/latex] и [latex]n \geq 0[/latex], то делаем вывод: точка принадлежит треугольнику.
  6. Если ни одно из вышеуказанных условий не выполняется, то точка не принадлежит треугольнику.

Ознакомиться с теоретическим материалом можно здесь.

Для запроса на выполнение следует перейти по ссылке.

Mif 17.1

Задача. Принадлежит ли точка [latex]\left(x;y \right)[/latex] фигуре на рисунке?

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

Два числа [latex] x[/latex], [latex]y[/latex] — координаты точки.

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

Слово «YES», если точка принадлежит треугольнику и «NO» ,  если не принадлежит.

17_1Тесты

[latex]x[/latex] [latex]y [/latex] Результат
4 -2  NO
2 1 YES
0 3 YES
5 0 NO
0 -1 NO

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

 

Код программы на ideone.com

Решение

Точка будет принадлежать треугольнику только при таких [latex]x[/latex] и [latex]y[/latex], что сумма их модулей не превышает 4. При выполнении условия выводим на экран: «YES». В противном случае — «NO».

Mif 6

Условие

Даны действительные числа [latex]x[/latex], [latex]y[/latex], [latex]z[/latex]. Могут ли они быть длинами сторон некоторого треугольника?

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

В одной строке задано три числа [latex]x[/latex], [latex]y[/latex] и [latex]z[/latex].

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

В одной строке вывести «YES»(без кавычек), если являются длинами некоторого невырожденного треугольника, или «NO»(без кавычек), если нет.

Тесты

Входные данные Выходные данные
1e1000 1e10000 1e-1000 NO
1e100 1e100 1e-100 YES
15.4 6.9 18.3 YES
17.55 37.67 88.98 NO
1000000 200000 30000 NO
1000000 1200000 900000 YES
3 4 5 YES
9 4 3 NO
99 10 47 NO

Код

Решение

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

ML18

Задача ML18

Условие задачи

Найти периметр треугольника по заданным координатам вершин [latex]A(x_1,y_1,z_1)[/latex], [latex]B(x_2,y_2,z_2)[/latex] и [latex]C(x_3,y_3,z_3)[/latex].

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

В одной строке заданы 9 чисел [latex]x_1, x_2, x_3, y_1, y_2, y_3, z_1, z_2, z_3[/latex] — координаты вершин треугольника [latex]ABC[/latex],  значения которых не превышают по модулю [latex]100[/latex].

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

Вывести периметр [latex]p[/latex] данного треугольника.

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

Тестирование

Входные данные ([latex]x_i, y_j, z_k; i, j, k= 1, 2, 3 [/latex]) Выходные данные
1 2 2 5 1  0 -1 3 5 10 16.0261556346
2 1 4 5 3 6 0 10.5 -2 -1 31.9047289894
3 15 26 13 32 18 56 80 0 -6.2 212.0962807371
4 -13 68 44 99 -100 70 0 2 1 450.5748518262
5 100 9 17 18 29 88 65 -16 0.36 310.4318979186

Реализация

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

  1. Задан произвольный треугольник [latex]ABC[/latex] с такими координатами вершин: [latex]A(x_1,y_1,z_1)[/latex], [latex]B(x_2,y_2,z_2)[/latex] и [latex]C(x_3,y_3,z_3)[/latex]. Обозначим стороны треугольника [latex] AB, BC, AC[/latex] как [latex]a, b, c[/latex] соответственно.
  2. Очевидно, что для того, чтобы вычислить периметр данного треугольника, нужно найти длины его сторон. Для этого воспользуемся формулой вычисления расстояния между двумя точками в пространстве. Получаем:[latex]a=\sqrt {(x_2-x_1)^2 + (y_2-y_1)^2 + (z_2-z_1)^2}[/latex]; [latex]b= \sqrt {(x_3-x_2)^2 + (y_3-y_2)^2 + (z_3-z_2)^2}[/latex]; [latex]c= \sqrt {(x_3-x_1)^2 + (y_3-y_1)^2 + (z_3-z_1)^2} [/latex].
  3. Зная значения сторон треугольника, вычисляем периметр, используя формулу. Получаем: [latex]p= a + b + c[/latex].

Подробнее о декартовой системе координат можно прочесть здесь.

Для запроса на выполнение следует перейти по ссылке.

 

ML23

Условие

Найти длины биссектрис [latex]a_1[/latex], [latex]b_1[/latex], [latex]c_1[/latex] треугольника, если известны длины противоположных сторон [latex]a[/latex], [latex]b[/latex], [latex]c[/latex].

Тестирование

Входные данные Выходные данные
1 6, 7, 9 7.35803, 6.49923, 4.67652
2 3.5, 4.5, 5.5 4.66027, 3.79967, 2.88195
3 100000, 100000, 100000 86602.5, 86602.5, 86602.5
4 1, 1.118034, 1.118034 1, 0.898056, 0.898056

Код

Решение

Для вычисления длины биссектрисы через три стороны произвольного треугольника воспользуемся формулой [latex]l_c = \frac{\sqrt{ab(a+b+c)(a+b-c)}}{a+b}[/latex], где:

  • [latex]l_c[/latex] — длина биссектрисы, проведенной к стороне [latex]c[/latex];
  • [latex]a[/latex], [latex]b[/latex], [latex]c[/latex] — стороны треугольника.

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

Можно заметить, что сумма [latex]a+b[/latex] встречается в формуле три раза. Для лучшей читаемости и компактности кода заменим a + b  на s :

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

Ссылки

Код программы на Ideone.com;

Формулы длины биссектрис в треугольнике;

Список задач на линейные вычисления.

ML 24

Условие задачи :

Треугольник задан длинами сторон. Найти радиус вписанной [latex]r[/latex] и описанной [latex]R[/latex] окружностей.

Тесты :

[latex]a[/latex] [latex]b[/latex] [latex]c[/latex] [latex]r[/latex] [latex]R[/latex]
3 4 5 1 2.5
7.5 10 13 2.45012 6.52361
1 3 4 0 inf
1 1 3 Не существует! Не существует!

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

Алгоритм :

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

Если треугольник существует, проводим следующие вычисления (порядок сохранен) :

  1. Вычисляем полупериметр [latex]p[/latex] треугольника: [latex]p[/latex] = [latex]\frac{a + b + c}{2}[/latex]
  2. Находим площадь [latex]S[/latex] по формуле Герона: [latex]S[/latex] = [latex]\sqrt{p(p-a)(p-b)(p-c)}[/latex]
  3. Вычисляем радиус [latex]r[/latex] вписанной окружности по формуле: [latex]r[/latex] = [latex]\frac{S}{p}[/latex]
  4. Вычисляем радиус [latex]R[/latex] описанной окружности по формуле: [latex]R[/latex] = [latex]\frac{abc}{4S}[/latex]

Работающая версия программы на Ideaone.com :

Ideone.com

Почитать про треугольник можно здесь :

Треугольник — Википедия

e-olymp 905. Какой треугольник?

Задача 
Определить вид треугольника (равносторонний, равнобедренный, разносторонний) по заданным длинам его сторон.

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

В единственной строке задано 3 целых числа — длины сторон треугольника. Длины сторон не превышают 100.

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

В единственной строке вывести 1, если треугольник равносторонний, 2 если равнобедренный и 3 если разносторонний.

Код

Тесты

Входные данные Выходные данные
1 5 5 5 1
2 4 5 4 2
3 4 5 6 3

Решение

Для решения задачи нам нужно уметь определять виды треугольников. Нам даны равносторонний, равнобедренный и разносторонний треугольники. У равностороннего треугольника все стороны равны, у равнобедренного равны лишь два бедра, а у разностороннего — стороны не равны.

Для начала задаем три переменные а, b и c, которые равны сторонам треугольника. Вводим их произвольно. Для того, чтобы определить какой это треугольник мы задаем параметры :

  1. если [latex]a=b=c[/latex] , то есть все стороны равны, то у нас равносторонний треугольник;
  2. если[latex] a=b [/latex]или [latex]b=c[/latex] или [latex]a=c[/latex] , то есть две из трех сторон треугольника равны, то у нас равнобедренный треугольник;
  3.  если [latex]a\neq b\neq c[/latex] , стороны не равны, то у нас разносторонний треугольник.

Задача взята с сайта.
Переход на страницу с полностью выполненным данным заданием здесь.

Какой треугольник?

Задача: 905. Какой треугольник? с сайта http://www.e-olimp.com.ua Определить вид треугольника (равносторонний, равнобедренный, разносторонний) по заданным длинам его сторон. Существование треугольника и корректность исходных данных гарантируется. Технические условия Входные данные В единственной строке задано 3 целых числа — длины сторон треугольника. Длины сторон не превышают 100. Выходные данные В единственной строке вывести 1, если треугольник равносторонний, 2 если равнобедренный и 3 если разносторонний.

Первая сторона Вторая сторона Третья сторона Результат
2 2 2 1
3 4 3 2
4 7 14 3

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

Задача решена методом моделирования. Вычисления проведены согласно условию, представленному в задаче. По условию задачи необходимо проверить каким является треугольник: равносторонним, равнобедренным или разносторонним. Для этого создаем массив из трех элементов(сторон треугольника), считываем его. Далее, если все элементы массива равны, то треугольник равносторонний, иначе, если две стороны равны, то он равнобедренный, если ни то, ни то не выполняется, то он разносторонний. Для проверки работы программы можно воспользоваться объектом. Ссылка на e-olimp: http://www.e-olymp.com/ru/submissions/2319469 Второй вариант:

http://www.e-olymp.com/ru/submissions/2319474

Код на Java:

Второй вариант:

Образец: Принадлежит ли точка треугольнику?

Задача. Даны три попарно не совпадающие и не лежащие на одной прямой точки [latex]A, B[/latex] и [latex]C[/latex], заданные своими координатами. Определить принадлежит ли точка [latex]D(x_d,y_d)[/latex] треугольнику [latex]ABC[/latex].
Сразу заметим, что задача легко обобщается для любого выпуклого многоугольника.

Тесты

В тестах нужно обязательно отразить следующие случаи:

  1. Точка строго вне треугольника
  2. Точка строго внутри треугольника
  3. Точка совпадает с одной из вершин треугольника
  4. Точка лежит на одной из сторон треугольника
  5. Точка лежит на продолжении одной из сторон треугольника
  6. Одна из сторон треугольника параллельна одной из осей координат
  7. Две стороны треугольника параллельны осям координат
xa ya xb yb xc yc xd yd Принадлежит?
-1 -1 1 -1 0 1 2 2 нет
-2 -2 1 -1 0 1 0 0 да
-1 -1 1 -1 0 1 0 1 да
-1 -1 1 -1 0 1 0.5 0 да
-1 -1 1 -1 0 1 1 3 нет
-1 -1 1 -1 0 1 0 0 да
0 0 2 0 0 2 1 1 да
0 0 2 0 0 2 5 5 нет

Плохое решение

В школьных учебниках такие задачи часто рекомендуют решать проверкой условия [latex]S_{ABC}=S_{ABD}+S_{BCD}+S_{CAD}[/latex]. При компьютерной реализации это приводит к необходимости сравнения двух действительных чисел на равенство. Эта крайне неприятная операция может быть проделана только с определённой степенью достоверности. Т.е. придётся проверять не превышает ли некоторого «с потолка» выбранного малого числа абсолютное [latex] \left| S_{ABD}+S_{BCD}+S_{CAD}-S_{ABC} \right| < \varepsilon[/latex] или относительное [latex]\left| 1-\frac{S_{ABD}+S_{BCD}+S_{CAD}}{S_{ABC}} \right| < \varepsilon[/latex] отклонение. Оставим эти вопросы для курса численных методов и методов приближённых вычислений и не будем идти по этому пути.

Неплохое решение

Начнём с простого наблюдения:

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

Запишем уравнение прямой, проходящей, например, через точки [latex]A[/latex] и [latex]B[/latex]. Получим [latex] \left( x-x_A \right) \left( y_B-y_A \right)-\left( y-y_A \right) \left( x_B-x_A \right) = 0[/latex]. Уравнение я записал в такой форме, чтобы не приходилось выполнять деление и переживать о нуле в знаменателе.

Неважно как называть стороны, важно научиться их различать.

Неважно как называть стороны, важно научиться их различать.

Теперь для любой точки [latex] \left( x;y \right)[/latex] мы можем вычислить левую часть приведенного равенства. Для точек, лежащих на прямой мы должны получать ноль. В тоже время прямая разобьёт плоскость на две полуплоскости. Точки лежащие в одной полуплоскости будут давать положительные значения. А точки из другой полуплоскости — отрицательные.
Мы готовы проверить первое условие — принадлежит ли точка [latex]D \left( x_d,y_d \right) [/latex] той же полуплоскости, что и точка [latex]C \left( x_c,y_c \right) [/latex] относительно прямой [latex] \left( AB \right) [/latex]? Для этого подставим обе точки в левую часть приведенного выше уравнения прямой и убедимся, что получены значения одного и того же знака. А если одна из точек даст точно ноль? Это означает, что точка лежит на прямой. По условию задачи это может быть только точка [latex]D[/latex]. Тогда она принадлежит треугольнику независимо от знака выражения, вычисленного для точки [latex]C[/latex].

Обратите внимание, что мы не утверждаем, что для любой точки на прямой наши приближённые вычисления обязаны дать точный ноль. Это было бы неверно. Мы только утверждаем, что если проведенные с доступной нам точностью вычисления всё же дали точный ноль, то мы вынуждены считать данную точку лежащей на данной прямой.

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

Плохой код

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

Нажмите здесь, чтобы выполнить этот код.

Приведенный код имеет существенные недостатки. Нам пришлось трижды записывать уравнение прямой проходящей через две точки и дважды подставлять в каждое из них координаты, чтобы проверить знак. Это значит, что нам пришлось шесть раз написать некоторую формулу с различными подстановками. При том подходе, что мы использовали имеем две проблемы. Во-первых, условие стало слишком сложным, чтобы его можно было легко воспринять. Во-вторых, и это гораздо хуже, такой код в [latex]\frac { 1-{ \left( 1-p \right) }^{ 6 } }{ p }[/latex] раз увеличивает вероятность совершить ошибку. Забавно, но это означает, что вероятность ошибки начинающего программиста увеличивается вдвое, а у опытного — в шесть раз. Хорошо, что опытные программисты не пишут такой код.

Неплохой код

Воспользуемся тем, что мы уже умеем создавать собственные функции для того, чтобы несколько сократить объём кода и сделать его более лёгким для восприятия.
Запишем условие на языке программирования С++:

Нажмите здесь, чтобы выполнить этот код.
Трудно сказать, стал ли код боле понятным или лаконичным. Однако можно точно сказать, что в нём отсутствуют повторяющиеся алгоритмические блоки. Все участки кода написаны строго по одному разу. Это уменьшает вероятность ошибки.

Чеширский код

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

Этот код содержит пока не изученные вами конструкции. Из-за этого он может показаться немного загадочным. Но если продолжать грызть гранит науки, то всё легко освоите. Или можно подождать…


Возможно слишком смело называть это хорошим кодом, но мы сделаем ещё один шаг в нужном направлении. В прошлом коде мы избавились от повторов в кодировании алгоритма. Однако остались повторы в кодировании данных. Вы заметили, что у нас четыре пары переменных? Т.е. просматривается структура состоящая из пары координат x и y, которую стоит объединить и назвать «точкой». Такие структуры в программировании на Си описывают с помощью ключевого слова struct. Это полезная промежуточная структура перед переходом к объектно-ориентированному программированию при помощи классов.

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