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

Ю2.30. Расстояние между отрезками

Задача

Задача из сборника задач по программированию Юркина А.Г. 2002 г.
Найти расстояние между двумя между двумя произвольно заданными на плоскости отрезками [latex]AB[/latex] и [latex]CD[/latex].

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

Координаты концов первого отрезка [latex]A[/latex] [latex](x_a, y_a)[/latex], [latex]B[/latex] [latex](x_b, y_b)[/latex].
Координаты концов второго отрезка [latex]C[/latex] [latex](x_c, y_c)[/latex], [latex]D[/latex] [latex](x_d, y_d)[/latex].

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

Расстояние между отрезками [latex]min[/latex].

Тесты

 Входные данные  Выходные данные
 № [latex]x_a[/latex] [latex]y_a[/latex] [latex]x_b[/latex] [latex]y_b[/latex] [latex]x_c[/latex] [latex]y_c[/latex] [latex]x_d[/latex] [latex]y_d[/latex] [latex]min[/latex]
 1  1  1  2  1  3  1  4  1  1
 2  0  0  5  5  1  1  2  2  0
 3  0  1  3  3  5  3  6  4  2
 4  0  0  7  0  0  8  5  3  3
 5  5  5  10  10  5  9  6  12  2.8284
 6  2  1  3  5  0  0  0  5  2
 7  -3  0  3  0  0  -3  0  3  0

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

Решение

Для начала проверим не пересекаются ли отрезки. Пусть для отрезка [latex]AB[/latex] [latex]x=t(x_b-x_a)+x_a[/latex], [latex]y=t(y_b-y_a)+y_a[/latex], а для [latex]CD[/latex] [latex]x=s(x_d-x_c)+x_c[/latex], [latex]y=s(y_d-y_c)+y_c[/latex] (где [latex]0\le t\le 1[/latex], [latex]0\le s\le 1[/latex] ). Если отрезки пересекаются, то выполняются равенства: [latex]t(x_b-x_a)-s(x_d-x_c)=x_c-x_a[/latex] и [latex]t(y_b-y_a)-s(y_d-y_c)=y_c-y_a[/latex]. Полученную систему уравнений решим методом Крамера: 
[latex]\Delta =\begin{pmatrix} x_b-x_a & \quad x_c-x_d \\ y_b-y_a & \quad y_c-y_d \end{pmatrix}=(x_b-x_a)(y_c-y_d)-(y_b-y_a)(x_c-x_d)[/latex] [latex]\Delta _1=\begin{pmatrix} x_{ b }-x_{ a } & \quad x_{ c }-x_{ a } \\ y_{ b }-y_{ a } & \quad y_{ c }-y_{ a } \end{pmatrix}=(x_b-x_a)(y_c-y_a)-(y_b-y_a)(x_c-x_a)[/latex] [latex]\Delta _2=\begin{pmatrix} x_{ c }-x_{ a } & \quad x_{ c }-x_{ d } \\ y_{ c }-y_{ a } & \quad y_{ c }-y_{ d } \end{pmatrix}=(y_c-y_d)(x_c-x_a)-(x_c-x_d)(y_c-y_a)[/latex].
Тогда [latex]t=\frac { \Delta_1 }{ \Delta } [/latex], а [latex]s=\frac { \Delta_2 }{ \Delta } [/latex]. Если [latex]0\le t\le 1[/latex], [latex]0\le s\le 1[/latex], а [latex]\Delta \neq 0[/latex], то отрезки пересекаются и расстояние между ними [latex]min[/latex] равно [latex]0[/latex], иначе с каждого конца отрезка попытаемся опустить высоту на противоположный. Если отрезок, на который опускаем высоту вертикальный, то поменяем местами координаты каждого конца отрезка и точки, с которой опускаем высоту (таким образом сохраним расстояние между точкой и отрезком, а отрезок станет горизонтальным). Пусть [latex]k[/latex] и [latex]d[/latex] — коэффициенты уравнения прямой, на которую опущена эта высота. Основание высоты будет находится на прямой в точке  [latex]Z[/latex], координаты [latex]Z[/latex] [latex](x_z, y_z)[/latex] можно найти по формуле [latex]y_z=kx_z+d[/latex]. Поскольку высота перпендикулярна отрезку — скалярное произведение их векторов равно [latex]0[/latex]. Тогда [latex](x_2-x_1)(x_3-x_z)+(y_2-y_1)(y_3-y_z)=0[/latex], соответственно [latex]x_z=\frac { x_3x_2-x_3x_1+y_2y_3-y_1y_3+y_1d-y_2d }{ ky_2-ky_1+x_2-x_1 } [/latex] (где [latex](x_3, y_3)[/latex] — координаты точки, с которой была опущена высота, [latex](x_1, y_1)[/latex] и [latex](x_2, y_2)[/latex] — координаты концов отрезка, принадлежащего прямой на которую опущена высота). Вычислим длину [latex]dl[/latex] каждой высоты, основание которой принадлежит одному из данных отрезков: [latex]dl=\sqrt { {(x_3-x_z)}^{2}+{(y_3-x_zk-d)}^{2} }[/latex](где [latex] (x_3, y_3)[/latex] — координаты точки, с которой была опущена высота). Минимальная длина высоты и будет наименьшим расстоянием между отрезками. В случае, если невозможно опустить высоты из одного отрезка на другой: расстояние между ними будет равно минимальному расстоянию между концами двух отрезков [latex]min=\sqrt { {( x_1-x_3) }^{ 2 }+{ (y_1-y_3) }^{ 2 } }[/latex] (где [latex](x_1, y_1)[/latex] — координаты одного из концов первого отрезка, а [latex](x_3, y_3)[/latex] — координаты одного из концов второго отрезка) .

Ссылки

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].

 

Ю1.26

Задача:

Треугольник задается координатами своих вершин на плоскости : [latex]A(x_{1} , y_{2})[/latex] , [latex]B(x_{2} , y_{2})[/latex] , [latex]C(x_{3} , y_{3})[/latex] . Найти длину и основание высоты, опущенной из вершины A на сторону ВС.

Тесты

[latex]x_{А}[/latex] [latex]y_{A}[/latex] [latex]x_{B}[/latex] [latex]y_{B}[/latex] [latex]x_{C}[/latex] [latex]y_{C}[/latex] Основание ([latex]BC[/latex]) Высота[latex]h[/latex] Комментарий
7 9 45 9 34 5 11 13 пройден
0.75 1 0.25 2 0.5 3 1 0 пройден
98 67 56 47 34 95 52 47 пройден
0 1 0 3 0 4 1 0 пройден

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

Код:

ссылка на C++ : http://ideone.com/fBfd8S

ссылка на Java : http://ideone.com/ut9G6J

 

Решение:

Для начала находим стороны треугольника :

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

и с помощью площади находим высоту :

и в конце выводим высоту и основание.

А59ж

Задача

Даны действительны числа [latex]x[/latex] , [latex]y[/latex]  . Определить , принадлежит ли точка с координатами  [latex]x[/latex] , [latex]y[/latex] заштрихованной части плоскости .

Безымянный

Тесты:

x y результат комментарий
-1.5 1 outside пройден
-0.5 0.5 inside пройден
0.5 0.5 inside пройден
1.5 1.5 outside пройден
-0.5 -0.5 inside пройден
-1 -1.5 outside пройден
1 -1.5 outside пройден

 

Ссылка на код C++ : http://ideone.com/JKdLjg

Ссылка на код Java : http://ideone.com/kWAdw2

Решение :

Решение задачи сводится к поиску условия, при котором точка будет принадлежать данной части плоскости. Далее вводим оператор условия «if» и ставим ограничения на [latex]x[/latex] и [latex]y[/latex].

Анализируем условие , при каких значениях [latex]x[/latex] и [latex]y[/latex] точка будет принадлежать условию , а при каких нет.Если вошла точка по координатам во все области -> точка принадлежит треугольнику или же наоборот .