Пересечение сторонами треугольника вписанной окружности. Подскажите алгоритм

@dzrkot · Регистрация: 11.09.2013

Author24 — интернет-сервис помощи студентам

На плоскости заданы множество точек и окружность радиусом R с центром в начале координат. Построить множество всех треугольников с вершинами в заданных точках, все три стороны которых пересекаются с окружностью, найти среди них треугольник с минимальной площадью.

задачу сделал для произвольного треугольника, не приходит в голову как проверять, что сторона треугольника пересекает окружность

@Denis123456789 · 27.04.2014, 15:39

Ну у Вас есть две точки начала(x1,y1) и конца(x2,y2) отрезка стороны треугольника, по ним можно составить уравнение прямой y=kx+b: k=(y2-y1)/(x2-x1), b=y1-x1*(y2-y1)/(x2-x1). Дальше находим общие точки прямой и окружности решая систему:
y=kx+b
x^2+y^2=R^2
Решение системы сводится к решению квадратного уравнения: (k^2+1)x^2+2*k*x*b-R^2+b^2=0;
Решаем его программно (коэф. изв, формулы изв.): если корней нет, значит не перес, если один-касаются, если два то пересекаются прямая и окружность, но нам нужно, чтобы пересекался отрезок прямой(сторона треуг.) с окр., поэтому проверяем полученные из корней точки на принадл. стороне треуг., если хотя бы один прин., то сторона пересекает окружность

@dzrkot zzzZZZ... 527 / 358 / 94 Регистрация: 11.09.2013 Сообщений: 2,041
		1
	Пересечение сторонами треугольника вписанной окружности. Подскажите алгоритм 27.04.2014, 14:47. Показов 1567. Ответов 1 Метки нет (Все метки) На плоскости заданы множество точек и окружность радиусом R с центром в начале координат. Построить множество всех треугольников с вершинами в заданных точках, все три стороны которых пересекаются с окружностью, найти среди них треугольник с минимальной площадью. задачу сделал для произвольного треугольника, не приходит в голову как проверять, что сторона треугольника пересекает окружность 0

@Denis123456789 43 / 43 / 21 Регистрация: 02.06.2013 Сообщений: 181
	27.04.2014, 15:39	2
	Ну у Вас есть две точки начала(x1,y1) и конца(x2,y2) отрезка стороны треугольника, по ним можно составить уравнение прямой y=kx+b: k=(y2-y1)/(x2-x1), b=y1-x1(y2-y1)/(x2-x1). Дальше находим общие точки прямой и окружности решая систему: y=kx+b x^2+y^2=R^2 Решение системы сводится к решению квадратного уравнения: (k^2+1)x^2+2kxb-R^2+b^2=0; Решаем его программно (коэф. изв, формулы изв.): если корней нет, значит не перес, если один-касаются, если два то пересекаются прямая и окружность, но нам нужно, чтобы пересекался отрезок прямой(сторона треуг.) с окр., поэтому проверяем полученные из корней точки на принадл. стороне треуг., если хотя бы один прин., то сторона пересекает окружность 1