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 47. Паркет из треугольников

Задача

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

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

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

Во входном файле в первой сроке через пробел заданы значения [latex]m[/latex], [latex]n[/latex] [latex]\left ( 1\leqslant n,m\leqslant 100 \right )[/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
3 5 4 15 22 3
5 3 2 6 12 2

Код 1

Для того, чтобы наш код был универсален для случая [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].
Важно отметить, что идея решения данного способа состоит в том, чтобы на позиции [latex]Search[firstNumberx — 1][/latex] стояло количество шагов, совершенных в ходе решения.

Код 2

Ссылки

Задача на e-olymp

Код_1 задачи на ideone

Код_2 задачи на ideone

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

Задача

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

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

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

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

Вывести высоту треугольника с точностью до сотых.

Тесты

# Входные данные Выходные данные
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

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

Решение

Для решения задачи нам понадобится формула для нахождения площади треугольника: [latex]S = \frac{1}{2} \cdot h \cdot c[/latex], где [latex]h[/latex] — высота, [latex]c[/latex] — сторона, к которой высота проведена. Вместо [latex]c[/latex] подставим [latex]h+a[/latex] (по условию задачи). Далее приходим к квадратному уравнению [latex]h^2 + a \cdot h — 2 \cdot S = 0[/latex]. Решив его, получим два корня. Второй корень нам не подходит, поскольку он меньше [latex]0[/latex], а длина не может быть отрицательной. Первый корень и будет ответом нашей задачи.

Ссылки

Ссылка на e-olymp

Ссылка на ideone

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]

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

Ссылка на источник

Mif 17.1

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

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

Два числа  xy — координаты точки.

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

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

Тесты

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

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

 

Решение

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

Ссылка на Ideone

http://ideone.com/GVQ1Yo

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

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

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

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

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

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

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

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

Код

www.ideone.com

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

Решение

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

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

  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], стороны не равны, то у нас разносторонний треугольник.

ML 24 Радиус вписанной/описанной в треугольник окружности

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

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

Тесты :

 a  b  c  r  R
3 4 5  1  90
2 2 6  Не существует  Не существует
3.1 4.1 5.1  1.033199  102.970967

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

Алгоритм :

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

Если условие не выполняется ,сообщаем об этом пользователю :

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

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

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

Ideone.com

ML 24

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

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

Тесты :

a b c r R
3 4 5 1 2.5
7.5 10 13 2.450117 6.5236096
1 3 4 0 inf
1 1 3 Не существует! Не существует!

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

Алгоритм :

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

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

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

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