Как найти медиану зная координаты вершины

Найти медиану треугольника по координатам вершин

Как найти медиану если даны координаты вершин треугольника?

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

Рассмотрим нахождение медианы на конкретном примере.

Дано: ΔABC,

1) Так как AF — медиана треугольника ABC, то F — середина BC.

Задачник «Векторный метод решения задач»

Обращаем Ваше внимание, что в соответствии с Федеральным законом N 273-ФЗ «Об образовании в Российской Федерации» в организациях, осуществляющих образовательную деятельность, организовывается обучение и воспитание обучающихся с ОВЗ как совместно с другими обучающимися, так и в отдельных классах или группах.

«Актуальность создания школьных служб примирения/медиации в образовательных организациях»

Свидетельство и скидка на обучение каждому участнику

Задачник «Векторный метод решения задач»

Составила: Казакова Ольга Сергеевна,

учитель математики МОУ «СОШ № 75» г. Саратова.

Данный задачник предназначен для изучения тем: «Векторы», «Действия с векторами», «Векторный метод решения задач». Инструктивное изложение материала, при постоянной практической пробе, даёт возможность изучить темы самостоятельно.

№ 1.Заполните таблицу. Основные понятия.

Решение и изображение

1)На плоскости отметьте точки A и B , постройте отрезок AB ;

2)На отрезке AB пусть точка A будет началом, а точка B – концом. Укажите стрелкой в конце отрезка направление из начала в конец. Вы получили отрезок, для которого указано, какая из его граничных точек считается началом, а какая – концом, то есть получили направленный отрезок или вектор .

3)Построен вектор , его можно обозначить и однострочной латинской буквой, например, , которая записывается над изображением вектора.

Сколько векторов можно провести, выбирая начало и конец среди данных на плоскости:

2)трёх точек, не лежащих на одной прямой;

3)четырёх точек, не лежащих на одной прямой?

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

Обозначение нулевого вектора: или символом .

1)Постройте отрезок AB , длина которого 4 см;

2)Постройте вектор .

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

Обозначение: = AB = 4.

Чему равна длина нулевого вектора?

3)Постройте вектор , длиной 7 см.

1)Постройте параллельные прямые p и m .

2)На прямой p постройте:

а)вектор , произвольной длины и направления;

б)вектор , произвольной длины и направления;

3)На прямой m постройте: вектор , произвольной длины и направления.

Ненулевые векторы называются коллинеарными , если они лежат либо на одной прямой, либо на параллельных прямых.

Нулевой вектор считается коллинеарным любому вектору.

4)Выпишите попарно коллинеарные векторы.

5)Постройте и обозначьте два произвольных вектора, которые являются не коллинеарными вектору . Будут ли они являться коллинеарными векторам , ?

Постройте два коллинеарных вектора.

Полученные векторы направлены одинаково или противоположно?

Если одинаково, то вы построили сонаправленные векторы. Обозначение:

 .

Если противоположно, то вы построили противоположно направленные векторы. Обозначение:  .

Начертите параллелограмм ABCD . Проведите векторы, начало и конец которых совпадают с какими-то двумя вершинами параллелограмма. Сколько существует пар векторов, которые являются:

1)коллинеарными друг другу;

Постройте векторы и , так, чтобы:

1)  ;

2) .

Вы построили равные векторы.

Векторы называются равными , если они сонаправлены и их длины равны.

№ 2.Заполните таблицу. Операции над векторами.

Решение и изображение

На плоскости произвольно выберите точку A , приняв её за начало, проведите вектор , произвольной длины и направления. Таким образом, вы отложили вектор от точки A .

Можно отложить от другой точки плоскости, вектор, равный данному вектору ?

Допустим, что вектор ненулевой, а точки A и B – его начало и конец.

1)Через произвольно взятую точку M плоскости проведите прямую p , параллельную AB (если M – точка прямой AB , то в качестве прямой p возьмём саму прямую AB ).

2)На прямой p отложите два противоположно направленных вектора и , длины которых равны отрезку AB .

Среди построенных векторов выберите тот, что сонаправлен с вектором , он и будет являться искомым вектором, равным вектору . К тому же такой вектор только один, что следует из построения.

А если вектор – нулевой? Ответьте самостоятельно.

Итак, от любой точки M можно отложить вектор, равный данному вектору , и при том только один.

1)Векторы и .

2)Произвольная точка A .

3)От точки A отложите вектор , равный вектору .

4)От точки B отложите вектор , равный вектору .

5)Вектор .

Вы, таким образом, выполнили построение сложения векторов и по правилу треугольника . Вектор называется суммой векторов и .

Докажем, что если и , то .

Рассмотрим случай, когда точки A , B , , точки B , C , и точки A , C , не лежат на одной прямой (остальные случаи рассмотрите самостоятельно).

а) ;

б) ;

в)Соединим точки A и , B и , C и ;

2)  – параллелограмм  ;

3)  – параллелограмм  ;

4)Из 2) и 3)   – параллелограмм;

5)Значит, . Доказано.

Вывод: при необходимости можно работать как с данными векторами, так и с равными им.

Законы сложения векторов.

Для любых векторов , и справедливы равенства:

(переместительный закон)

(сочетательный закон)

Доказательство законов проведите самостоятельно, опираясь на подсказки:

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

Для доказательства второго закона достаточно несколько раз применить правило треугольника для сложения векторов, последовательно отложенных от концов предыдущих векторов.

1)Произвольная точка A ;

2)Неколлинеарные векторы и ;

3) От точки A отложите вектор , равный вектору .

4)От точки A отложите вектор , равный вектору .

5)Постройте параллелограмм ABCD ;

6) .

Вы построили сложение векторов и по правилу параллелограмма сложения неколлинеарных векторов.

Как сложить несколько векторов?

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

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

Вы выполнили построение сложения нескольких векторов, пользуясь правилом многоугольника .

Подумайте, чему будет равна сумма векторов, если начало первого вектора совпадает с концом последнего?

Разностью векторов и называется такой вектор, сумма которого с вектором равна вектору .

Вектор называется противоположным вектору , если векторы и имеют равные длины и противоположно направлены. Обозначение: . .

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

На прямой p от любой точки O отложите вектор , от конца вектора отложите вектор . Длина построенного суммарного вектора, равна или .

Произведением ненулевого вектора на число k называется такой вектор , длина которого равна , причём векторы и сонаправлены при k  0 и противоположно направлены при k .

Произведением нулевого вектора на любое число считается нулевой вектор.

Из определения следует:

1)произведение любого вектора на число нуль есть нулевой вектор;

2)для любого числа k и любого вектора векторы и коллинеарны.

Свойства умножения вектора на число.

Для любых чисел k , l и любых векторов , справедливы равенства:

(сочетательный закон)

(первый распределительный закон)

(второй распределительный закон)

На прямой p от произвольно выбранной точки O отложите: вектор , длиной 1 см; вектор , сонаправленный с вектором , длиной 2 см; вектор , противоположно направленный с вектором , длиной 3 см.

Попробуем выразить векторы и через вектор .

Во сколько раз длины этих векторов отличаются от длины вектора ?

; ;

 ,  , т. е. векторы , и коллинеарны друг другу, значит, можно воспользоваться леммой.

Если векторы и коллинеарны и , то существует такое число k , что .

Итак, можем выразить: , .

От произвольной точки O отложите векторы и , и – произвольные данные векторы. Если и не являются сонаправленными, то лучи OA и OB образуют угол AOB , градусную меру которого обозначьте буквой α. Будем говорить, что угол между векторами и равен α. Обозначение: .

Если  , то

Если , то векторы и называются перпендикулярными.

Скалярным произведением двух векторов называется произведение их длин на косинус угла между ними.

Напишите формулу скалярного произведения для случаев, когда:

;

;

.

Сделайте вывод, о том, в каком случае скалярное произведение двух векторов равно нулю.

Напишите формулу скалярного произведения для случая, когда вектор скалярно умножается на себя. В этом случае скалярное произведение называется скалярным квадратом . Обозначение: .

Итак, перечислите все операции над векторами.

№ 3.Решая задачи, заполните пустые ячейки в таблице.

k , что ,

точки M и N совпадают

точка C принадлежит прямой AB

, или
, или

точка С – середина отрезка AB

точка D разбивает отрезок AC так, что AD : DC = m : n

Заполняя таблицу, вы пользовались векторным методом решения задач.

Векторный метод – один из наиболее общих методов решения геометрических задач.

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

Далее вам необходимо самостоятельно решать задачи. После решения каждой задачи делайте вывод о её значимости. Если результат задачи возможно использовать для решения других, то заносите его в таблицу № 3. Таким образом, вы получите набор базовых задач, на основании которых решаются более сложные.

1)Докажите, что средняя линия треугольника параллельна его третьей стороне и равна её половине.

2)Докажите, что средняя линия трапеции параллельна её основанию и её длина равна полусумме длин её оснований.

3)Если средняя линия четырёхугольника равна полусумме длин её оснований (сторон, не имеющих общей точки со средней линией), то этот четырёхугольник является трапецией или параллелограммом.

4)Около окружности описана равнобочная трапеция ABCD . Точки E и K – точки касания этой окружности с боковыми сторонами AB и CD . Докажите, что отрезок EK параллелен основаниям трапеции.

5)Докажите, что биссектриса угла треугольника делит его сторону на отрезки, пропорциональные прилежащим сторонам. Выразите биссектрису через угол треугольника, который она делит пополам, и через стороны этого угла.

6)Если точки M и N делят отрезки AB и CD соответственно в равных отношениях так, что AM : MB = CN : ND = m : n , то выполняется равенство: .

7)В треугольнике ABC через M обозначена точка пересечения медиан. Докажите, что .

8)Пусть M – точка пересечения медиан треугольника ABC , O – произвольная точка. Докажите, что .

9)Пусть H – точка пересечения высот треугольника ABC , O – центр описанной окружности. Докажите, что .

10)Докажите, что три точки A , B , C ( A ≠ B ) лежат на одной прямой тогда и только тогда, когда имеет место равенство, , в котором α+β=1, где O – некоторая точка.

11)Докажите, что центр описанной окружности

12)Докажите, что если точки пересечения диагоналей четырёхугольника и середины двух его противоположных сторон лежат на одной прямой, то этот четырёхугольник – трапеция или параллелограмм.

13)Докажите, что медианы треугольника пересекаются в одной точке и делятся ею в отношении 2:1, считая от вершины.

14)Докажите, что биссектрисы треугольника пересекаются в одной точке.

15)Докажите, что высоты треугольника пересекаются в одной точке.

16)Докажите, что четырёхугольник является параллелограммом тогда и только тогда, когда его диагонали в точке пересечения делятся пополам.

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

18)Найти косинус угла между диагоналями прямоугольника, стороны которого равны a и b .

19)Докажите, что диагонали ромба взаимно перпендикулярны.

20)Докажите, что вписанный угол, опирающийся на диаметр окружности, — прямой.

21)Докажите, что если в треугольнике длины его сторон a , b , c связаны соотношением , то угол этого треугольника, лежащий против стороны длины c , — прямой.

22)Даны стороны a , b , c треугольника. Найдите медианы , , , проведённые к этим сторонам.

23)В треугольнике со сторонами a , b , c найти длину высоты , опущенную на сторону c .

24)В треугольнике со сторонами a , b , c найти длину биссектрисы , проведённой к стороне c .

25)Докажите, что сумма квадратов длин диагоналей параллелограмма равна сумме квадратов длин всех его сторон.

26)Докажите, что сумма квадратов длин диагоналей трапеции равна сумме квадратов длин её боковых сторон плюс удвоенное произведение длин оснований.

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

28)Докажите, диагонали прямоугольника равны между собой.

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

30)В четырёхугольнике ABCD прямая, проведённая через вершину A параллельна стороне BC , пересекает диагональ BD в точке M , а прямая проведённая через вершину B параллельно стороне AD , пересекает диагональ AC в точке N . Докажите, что MN || DC .

31)Четыре окружности радиуса R пересекаются по три в точках M и N , и по две в точках A , B , C , D . Докажите, что ABCD – параллелограмм.

32)Пусть K , L , M , N – середины отрезков AB , BC , CD , DE пятиугольника ABCDE , а точки P и Q – середины отрезков KM и LN соответственно. Докажите, что отрезок PQ в четыре раза меньше стороны AE и параллелен ей.

33)В плоскости даны четырёхугольник ABCD и точка M . Докажите, что точки, симметричные точке M относительно середин сторон этого четырёхугольника, являются вершинами параллелограмма.

34)На диагоналях AC и CE правильного шестиугольника ABCDEF взяты точки M и N соответственно, такие, что AM : AC = CN : CE = λ. Известно, что точки B , M , N лежат на одной прямой. Найдите λ.

35)Дан параллелограмм ABCD ( AD || BC , AB || CD ). На стороне AD выбрана точка K , а на AC – точка L так, что 5 AK = AD , 6 AL = AC . Докажите, что KL || BL и найдите отношение их длин.

36)Точки M и K на сторонах AB и BC треугольника ABC таковы, что AM : MB =3:4, CK : KB =2:3. Отрезки AK и CM пересекаются в точке N . Найдите отношение AN : NK .

37)Точка K на стороне AC и точки L , M на стороне BC треугольника ABC таковы, что AK : KC = CL : LB = BM : MC =1:2, N – середина стороны AC . Найти отношение, в котором точка пересечения отрезков KL и MN делит отрезок KL .

38)Через середину E медианы треугольника ABC проведена прямая AE , пересекающая сторону BC в точке F . Вычислить: AE : EF и CF : FB .

39)Дан параллелограмм ABCD . Точка M делит сторону AD в отношении p , т. е. AM : MD = p ; точка N делит сторону DC в отношении q , т. е. DN : NC = q . Прямые BM и AN пересекаются в точке S . Вычислить отношения AS : SN и BS : SM .

40)В параллелограмме ABCD сторона AD разделена на n равных частей и первая точка деления M (считая от A ) соединена с B . В каком отношении делит точка N диагональ AC и отрезок MB ?

41)В треугольнике ABC проведена медиана CM . Прямая l пересекает отрезки CA , CM , CB в точках , , соответственно. Докажите равенство .

42)На сторонах AC и BC треугольника ABC взяты точки M и D так, что AM = AC , BD = BC , а на прямой AD – точка N так, что AN = AD . Доказать, что точки M , N и B лежат на одной прямой. Какую часть от отрезка MB составляет отрезок MN ?

43)На стороне AD и диагонали AC параллелограмма ABCD взяты точки M и N так, что AM = AD , AN = AC . Доказать, что точки M , N и B лежат на одной прямой. В каком отношении делит точка N отрезок MB ?

44)На стороне AB треугольника ABC дана точка P , через которую проведены прямые параллельно его медианам A и A и пересекающие соответственно стороны треугольника в точках и . Докажите, что середина отрезка (точка E ), а также точка P и точка G пересечения медиан треугольника лежат на одной прямой и найдите отношение длин отрезков EG и EP .

45)Докажите, что точки пересечения диагоналей трапеции, боковых сторон, а также середины оснований лежат на одной прямой.

46)Через точку P – внутреннюю точку параллелограмма ABCD – проведены прямая KM || AD и прямая LN || AB , пересекающие стороны AB , BC , CD , DA параллелограмма в точках K , L , M , N соответственно. Q – точка пересечения средних линий четырёхугольника KLMN , S – точка пересечения диагоналей параллелограмма ABCD . Докажите, что Q – середина отрезка PS .

47)Пусть , , – середины сторон BC , AC , AB треугольника ABC . Доказать, что точки пересечения медиан треугольника ABC и треугольника совпадают.

48)Пусть ABCDEF – произвольный шестиугольник и U , V , W , X , Y , Z – середины его сторон. Докажите, что центры тяжести (т. е. точки пересечения медиан) треугольника UWY и треугольника VXZ совпадают.

49)Докажите, что прямая, соединяющая середины оснований трапеции, и продолжения боковых сторон трапеции пересекаются в одной точке.

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

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

52)В треугольнике ABC длины сторон связаны соотношением . Докажите, что медианы, проведённые к сторонам AC и BC , взаимно перпендикулярны.

53)Найдите косинус угла между медианами прямоугольного равнобедренного треугольника, проведёнными к его катетам.

54)Найти косинус угла между медианами равнобедренного треугольника, проведёнными к его боковым сторонам, при условии, что угол при вершине равен α.

55)Найти косинус угла при вершине равнобедренного треугольника, если медианы, проведённые к его боковым сторонам, а) перпендикулярны; б) образую угол .

56)В треугольнике две стороны равны 2 и 4, а угол между ними равен . Найти угол ψ между короткой стороной и медианой, проведённой к третьей стороне.

57)В окружности с центром O радиуса r вписан четырёхугольник ABCD . Доказать, что если , то диагонали четырёхугольника взаимно перпендикулярны.

58)В прямоугольнике ABCD опущен перпендикуляр BK на диагональ AC . Точки M и N – середины отрезков AK и CD соответственно. Докажите, что угол BMN прямой.

59)На стороне AB треугольника ABC с углом ABC , равным α , расположена точка K , причём AK = BC . Пусть P – середина BK , M – середина AC . Найдите угол APM .

60)Точка K – середина стороны AB квадрата ABCD , а точка M лежит на диагонали AC , причём AM : MC = 3 : 1. Докажите, что угол KMD равен .

61)На сторонах AB и AC треугольника ABC во внешнюю сторону построены квадраты AMNB и CKLA . Докажите, что медиана AP треугольника ABC перпендикулярна прямой ML .

62)На стороне AB треугольника ABC дана точка D . Выразить расстояние CD через длины сторон данного треугольника a , b , c и расстояния AD = m и DB = n .

63)Выразить расстояние от заданной точки O до точки M пересечения медиан треугольника ABC через длины сторон треугольника BC = a , AC = b , AB = c и расстояния от точки O до вершин треугольника OA = , OB = , OC = .

64)В параллелограмме ABCD точка K – середина стороны BC , а точка M – середина стороны CD . Найдите AD , если AK = 6, AM = 3,  KAM = .

Список использованной литературы

Атанасян Л.С. и др. Геометрия. Учебник для 7-9 кл. общеобразовательных учреждений. – М.: Просвещение, 2003.

Атанасян Л.С., Бутузов В.Ф., Кадомцев С.Б. и др. Геометрия. 10-11 классы: учеб. для общеобразоват. учреждений: базовый и профил. уровни. – М.: Просвещение, 2009.

Бутузов В.Ф., Кадомцев С.Б., Позняк Э.Г., Шестаков С.А., Юдина И.И. Планиметрия. Пособие для углубленного изучения математики – М.: ФИЗМАТЛИТ, 2005.

Василевский А.Б. Методы решения геометрических задач. – Минск: Вышэйш. школа, 1965.

Габович И.Г. Алгоритмический подход к решению геометрических задач. – М.: Просвещение, 1996.

Гордин Р.К. Геометрия. Планиметрия 7-9 кл. – М.: МЦНМО, 2006.

Готман Э.Г., Скопец З.А. Решение геометрических задач аналитическим методом: Пособие для учащихся 9 и 10 кл. – М.: Просвещение, 1979.

Гусев В. А. и др. Практикум по элементарной математике: Геометрия: Учеб. пособие для студентов физ.-мат. спец. пед. ин-тов и учителей. – М.: Просвещение, 1992.

Зеленяк О. П. Решение задач по планиметрии. Технология алгоритмического подхода на основе задач-теорем. Моделирование в среде Turbo Pascal. – Киев, Москва: ДиаСофтЮП, ДМК Пресс, 2008.

Шарыгин И. Ф. Геометрия. 7 – 9 кл.: Учеб. для общеобразоват. учеб. завед. – М.: Дрофа, 2001.

Шарыгин И.Ф. Решение задач: Учеб. пособие для 10 кл. общеобразоват. учреждений. – М.: Просвещение, 1994.

Шестаков С. А. Векторы на экзаменах. Векторный метод в стереометрии. – М.: МЦНМО, 2005.

Мой любимый алгоритм: нахождение медианы за линейное время

Нахождение медианы за O(n log n)

Самым прямолинейным способом нахождения медианы является сортировка списка и выбор медианы по её индексу. Самая быстрая сортировка сравнением выполняется за O(n log n) , поэтому от неё зависит время выполнения 1 , 2 .

У этого способа самый простой код, но он определённо не самый быстрый.

Нахождение медианы за среднее время O(n)

Следующим нашим шагом будет нахождение медианы в среднем за линейное время, если нам будет везти. Этот алгоритм, называемый «quickselect», разработан Тони Хоаром, который также изобрёл алгоритм сортировки с похожим названием — quicksort. Это рекурсивный алгоритм, и он может находить любой элемент (не только медиану).

1. Выберем индекс списка. Способ выбора не важен, на практике вполне подходит и случайный. Элемент с этим индексом называется опорным элементом (pivot).
2. Разделим список на две группы:
   1. Элементы меньше или равные pivot, lesser_els
   2. Элементы строго большие, чем pivot, great_els
3. Мы знаем, что одна из этих групп содержит медиану. Предположим, что мы ищем k-тый элемент:
   • Если в lesser_els есть k или больше элементов, рекурсивно обходим список lesser_els в поисках k-того элемента.
   • Если в lesser_els меньше, чем k элементтов, рекурсивно обходим список greater_els . Вместо поиска k мы ищем k-len(lesser_els) .

Вот пример алгоритма, выполняемого для 11 элементов:

Чтобы найти с помощью quickselect медиану, мы выделим quickselect в отдельную функцию. Наша функция quickselect_median будет вызывать quickselect с нужными индексами.

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

Доказательство среднего времени O(n)

В среднем pivot разбивает список на две приблизительно равных части. Поэтому каждая последующая рекурсия оперирует с 1 ⁄₂ данных предыдущего шага.

Существует множество способов доказательства того, что этот ряд сходится к 2n. Вместо того, чтобы приводить их здесь, я сошлюсь на замечательную статью в Википедии, посвящённую этому бесконечному ряду.

Quickselect даёт нам линейную скорость, но только в среднем случае. Что, если нас не устраивает среднее, и мы хотим гарантированного выполнения алгоритма за линейное время?

Детерминированное O(n)

В предыдущем разделе я описал quickselect, алгоритм со средней скоростью O(n) . «Среднее» в этом контексте означает, что в среднем алгоритм будет выполняться за O(n) . С технической точки зрения, нам может очень не повезти: на каждом шаге мы можем выбирать в качестве pivot наибольший элемент. На каждом этапе мы сможем избавляться от одного элемента из списка, и в результате получим скорость O(n^2) , а не O(n) .

С учётом этого, нам нужен алгоритм для подбора опорных элементов. Нашей целью будет выбор за линейное время pivot, который в худшем случае удаляет достаточное количество элементов для обеспечения скорости O(n) при использовании его вместе с quickselect. Этот алгоритм был разработан в 1973 году Блумом (Blum), Флойдом (Floyd), Праттом (Pratt), Ривестом (Rivest) и Тарьяном (Tarjan). Если моего объяснения вам не хватит, то можете изучить их статью 1973 года. Вместо того, чтобы описывать алгоритм, я подробно прокомментирую мою реализацию на Python:

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

Красным овалом обозначены медианы фрагментов, а центральным кругом — медиана медиан. Не забывайте, мы хотим, чтобы pivot разделял список как можно ровнее. В худшем возможном случае каждый элемент в синем прямоугольнике (слева вверху) будет меньше или равен pivot. Верхний правый прямоугольник содержит 3 ⁄₅ половины строк — 3/5*1/2=3/10 . Поэтому на каждом этапе мы избавляемся по крайней мере от 30% строк.

Но достаточно ли нам отбрасывать 30% элементов на каждом этапе? На каждом этапе наш алгоритм должен выполнять следующее:

• Выполнять работу O(n) по разбиению элементов
• Для рекурсии решать одну подзадачу размером в 7 ⁄₁₀ от исходной
• Для вычисления медианы медиан решать одну подзадачу размером с 1 ⁄₅ от исходной

В результате мы получаем следующее уравнение полного времени выполнения T(n) :

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

Подводим итог

У нас есть quickselect, алгоритм, который находит медиану за линейное время при условии наличия достаточно хорошей опорного элемента. У нас есть алгоритм медианы медиан, алгоритм O(n) для выбора опорного элемента (который достаточно хорош для quickselect). Соединив их, мы получили алгоритм нахождения медианы (или n-ного элемента в списка) за линейное время!

Медианы за линейное время на практике

В реальном мире почти всегда достаточно случайного выбора медианы. Хотя подход с медианой медиан всё равно выполняется за линейное время, на практике его вычисление длится слишком долго. В стандартной библиотеке C++ используется алгоритм под названием introselect, в котором применено сочетание heapselect и quickselect; предел его выполнения O(n log n) . Introselect позволяет использовать обычно быстрый алгоритм с плохим верхним пределом в сочетании с алгоритмом, который медленнее на практике, но имеет хороший верхний предел. Реализации начинают с быстрого алгоритма, но возвращаются к более медленному, если не могут выбрать эффективные опорные элементы.

В завершение приведу сравнение элементов, используемых в каждой из реализаций. Это не скорость выполнения, а общее количество элементов, которые рассматривает функция quickselect. Здесь не учитывается работа по вычислению медианы медиан.

Именно этого мы и ожидали! Детерминированный опорный элемент почти всегда рассматривает при quickselect меньшее количество элементов, чем случайный. Иногда нам везёт и мы угадываем pivot с первой попытки, что проявляется как впадины на зелёной линии. Математика работает!

1. Это может стать интересным применением поразрядной сортировки (radix sort), если вам нужно найти медиану в списке целых чисел, каждое из которых меньше 2 32 .
2. На самом деле в Python используется Timsort, впечатляющее сочетание теоретических пределов и практической скорости. Заметки о списках в Python.

Решить треугольник Онлайн по координатам

Данный онлайн-сервис вычисляет (показываются промежуточные расчёты) следующие параметры треугольника:

1) длины и уравнения сторон, медиан, средних линий, высот, серединных перпендикуляров, биссектрис;

2) система линейных неравенств, определяющих треугольник;

2) уравнения прямых, проходящих через вершины параллельно противолежащим сторонам;

3) внутренние углы по теореме косинусов;

4) площадь треугольника;

5) точка пересечения медиан (центроид) и точки пересечения медиан со сторонами;

10) параметры вписанной и описанной окружностей и их уравнения.

Внимание! Этот сервис не работает в браузере IE (Internet Explorer).

Запишите координаты вершин треугольника и нажмите кнопку.

Математический форум (помощь с решением задач, обсуждение вопросов по математике).

Если заметили ошибку, опечатку или есть предложения, напишите в комментариях.

Пример 1:

Построить треугольник, вершины которого находятся в точках А (2; 4), В (-3; 2), С (-3; -4). Найти:

1) уравнения сторон треугольника АВС;

2) координаты точки пересечения медиан;

3) длину и уравнение высоты, опущенной из вершины А;

4) площадь треугольника.

Решение от преподавателя:

Уравнение, прямой проходящей через две точки
1) Уравнения сторон треугольника АВС

2) Координаты точки пересечения медиан

Медиана – отрезок, соединяющий вершину треугольника с серединой противоположной стороны.

Координаты т. E как середины отрезка ВС.

Уравнение АЕ

Координаты т. К как середины отрезка АВ.

Уравнение СК

3) Длина и уравнение высоты, опущенной из вершины А

Расстояние от точки до прямой

Уравнение прямой, проходящей через точку перпендикулярно другой прямой

Уравнение AN

4) Площадь треугольника

Длина ВС

Пример 2:

Решение от преподавателя:

Пример 3:

По координатам вершин треугольника ABC найти:

• периметр треугольника;
• уравнения сторон AB и BC;
• уравнение высоты AD; угол ABC;
• площадь треугольника.

Сделать чертеж.

А(1; 2); В (–1; 2); С(3; 0).

Решение от преподавателя:

Пример 4:

Даны координаты вершин треугольникаА, В, С.

Требуется найти:

1) уравнение и длину стороны ВС;

2) уравнение и длину высоты, проведённой из вершиныА;

3) уравнение медианы, проведённой из вершиныА;

4) площадь треугольника.

Сделать чертёж.

А(4;-3), B(-2;-1), C(3;-2).

Решение от преподавателя:

Пример 5:

Решение от преподавателя:

1)

2)

3) Находим координаты точки М – середины стороны ВС:

Определяем длину медианы АМ:

4) Составляем уравнение медианы – прямой АМ:

5) Если ВН – высота, проведенная из вершины В к стороне АС, то, поскольку ВН проходит через точку В перпендикулярно вектору , то составляем уравнение высоты по формуле , где (a,b) – координаты вектора перпендикулярного искомой прямой,  – координаты точки, принадлежащей этой прямой. Находим координаты вектора АС:

и подставляем в формулу, ,

6) Длину высоты ВН находим как расстояние от точки В до прямой АС:

7) Площадь треугольника АВС:

Находим угол ВАС треугольника:

9) Составляем уравнение прямой, проходящей через т.А параллельно ВС:

Ответ:

Пример 6:

Решение от преподавателя:

1. Уравнение прямой 
   Прямая, проходящая через точки A₁(x₁; y₁) и A₂(x₂; y₂), представляется уравнениями: 
   
   Уравнение прямой AB 
   Каноническое уравнение прямой: 
   
   или 
   
   или 
   y = ^-3/₇x + ¹⁶/₇ или 7y + 3x — 16 = 0 
2. Обозначим середину стороны AB буквой М. Тогда координаты точки M найдем по формулам деления отрезка пополам. 
   
   
   M(3;1) 
   Уравнение медианы CM найдем, используя формулу для уравнения прямой, проходящей через две заданные точки. Медиана CМ проходит через точки C(-8;2) и М(3;1), поэтому: 
   Каноническое уравнение прямой: 
   
   или 
   
   или 
   y = ^-1/₁₁x + ¹⁴/₁₁ или 11y + x — 14 = 0 
3. Уравнение высоты через вершину C 
   Прямая, проходящая через точку N₀(x₀;y₀) и перпендикулярная прямой Ax + By + C = 0 имеет направляющий вектор (A;B) и, значит, представляется уравнениями: 
   
   Найдем уравнение высоты через вершину C 
   
   y = ⁷/₃x + ⁶²/₃ или 3y -7x — 62 = 0
4. уравнение параллельной прямой AB, проходящей через точку (-8,2)
   Уравнение прямой AB: y = ^-3/₇x + ¹⁶/₇
   Уравнение KN параллельно AB находится по формуле:
   y — y₀ = k(x — x₀)
   Подставляя x₀ = -8, k = ^-3/₇, y₀ = 2 получим:
   y-2 = ^-3/₇(x-(-8))
   или
   y = ^-3/₇x — ¹⁰/₇ или 7y + 3x +10 = 0

Пример 7:

Даны координаты вершин треугольника: A(1,1), B(4,13), C(10,5). 

Решение от преподавателя:

4) Уравнение высоты через вершину C 
Прямая, проходящая через точку N₀(x₀;y₀) и перпендикулярная прямой Ax + By + C = 0 имеет направляющий вектор (A;B) и, значит, представляется уравнениями: 

Найдем уравнение высоты через вершину C 

y = ^-1/₄x + ¹⁵/₂ или 4y +x -30 = 0 
Данное уравнение можно найти и другим способом. Для этого найдем угловой коэффициент k₁ прямой AB. 
Уравнение AB: y = 4x -3, т.е. k₁ = 4 
Найдем угловой коэффициент k перпендикуляра из условия перпендикулярности двух прямых: k₁*k = -1. 
Подставляя вместо k₁ угловой коэффициент данной прямой, получим: 
4k = -1, откуда k = ^-1/₄ 
Так как перпендикуляр проходит через точку C(10,5) и имеет k = ^-1/₄,то будем искать его уравнение в виде: y-y₀ = k(x-x₀). 
Подставляя x₀ = 10, k = ^-1/₄, y₀ = 5 получим: 
y-5 = ^-1/₄(x-10) 
или 
y = ^-1/₄x + ¹⁵/₂ или 4y + x — 30 = 0 
Найдем точку пересечения с прямой AB: 
Имеем систему из двух уравнений: 
y -4x +3 = 0 
4y + x — 30 = 0 
Из первого уравнения выражаем y и подставим во второе уравнение. 
Получаем: 
x = ⁴²/₁₇ 
y = ¹¹⁷/₁₇ 
D(⁴²/₁₇;¹¹⁷/₁₇) 
Длина высоты треугольника, проведенной из вершины C 
Расстояние d от точки M₁(x₁;y₁) до прямой Ax + By + С = 0 равно абсолютному значению величины: 

Найдем расстояние между точкой C(10;5) и прямой AB (y -4x +3 = 0) 

5,7) Уравнение медианы треугольника 
Обозначим середину стороны BC буквой Е. Тогда координаты точки Е найдем по формулам деления отрезка пополам. 


Е(7;9) 
Уравнение медианы AЕ найдем, используя формулу для уравнения прямой, проходящей через две заданные точки A(1;1) иЕ(7;9), поэтому: 
Каноническое уравнение прямой: 

или 

или 
y = ⁴/₃x ^-1/₃ или 3y -4x +1 = 0 
Найдем длину медианы. 
Расстояние между двумя точками выражается через координаты формулой: 

6) CD—диаметр окружности. Центр окружности точка О лежит в середине отрезка CD

Уравнение окружности  (x-x₀)²+(y-y₀)²=r²

(x-106/17)²+(y-101/17)²=256/17 

Уравнение прямой, параллельной CD, проходящей через точку A 

Пример 8:

Решение от преподавателя:

Точка D – середина стороны АВ , ее координаты равны полусумме координат А и В. Получим D(1, -1)

Пример 9:

Даны координаты вершин треугольника АВС: А (3,-2), В (-5,-4),  С (-1,6).

Найдите: 1) уравнения сторон треугольника АВ, ВС и АС;

2) периметр (сумму длин) треугольника;

3) уравнение высоты СН;

4) расстояние d от точки С до прямой АВ;

5) сделайте чертеж.

Решение от преподавателя:

Решение.

1) уравнения сторон треугольника АВ, ВС и АС

Уравнение, прямой проходящей через две точки

2) периметр (сумму длин) треугольника

Расстояние между двумя точками

3) уравнение высоты СН

Уравнение прямой, проходящей через точку перпендикулярно другой прямой

4) расстояние d от точки С до прямой АВ

Расстояние от точки до прямой

Пример 10:

Даны вершины A (x₁; y₁), B (x₂; y₂), C (x₃; y₃)    треугольника.

Найти: 1) уравнение стороны AB;

2) уравнение медианы, проведенной из вершины C;

3) уравнение высоты, проведенной из вершины C ;

4) уравнение прямой, проходящей через вершину C параллельно стороне AB .

A (6; 0), B (2; − 6), C (−3; −9).

Решение от преподавателя:

Пример 11:

Решение от преподавателя:

Пример 12:

Дан треугольник  с координатами вершин найти:

а) длину стороны AB;

б) косинус угла ABC;

в) площадь треугольника ABC (через векторное произведение);

Решение от преподавателя:

Пример 13:

Решение от преподавателя:

Даны координаты вершин треугольника: A(6,0), B(2,-6), C(-3,-9). 
1) Уравнение прямой 
Прямая, проходящая через точки A₁(x₁; y₁) и A₂(x₂; y₂), представляется уравнениями: 

Уравнение прямой AB 
Каноническое уравнение прямой: 

или 

или 
y = ³/₂x -9 или 2y -3x +18 = 0 

2) Уравнение медианы треугольника 
Обозначим середину стороны AB буквой М. Тогда координаты точки M найдем по формулам деления отрезка пополам. 


M(4;-3) 
Уравнение медианы CM найдем, используя формулу для уравнения прямой, проходящей через две заданные точки. Медиана CМ проходит через точки C(-3;-9) и М(4;-3), поэтому: 
Каноническое уравнение прямой: 

или 

или 
y = ⁶/₇x ^-45/₇ или 7y -6x +45 = 0 
3) Уравнение высоты через вершину C 
Прямая, проходящая через точку N₀(x₀;y₀) и перпендикулярная прямой Ax + By + C = 0 имеет направляющий вектор (A;B) и, значит, представляется уравнениями: 

Найдем уравнение высоты через вершину C 

y = ^-2/₃x -11 или 3y +2x + 33 = 0 
4) Уравнение прямой, параллельной AB, проходящей через С(-3,-9) 
Уравнение прямой AB: 2y -3x +18 = 0 
Уравнение СN параллельно AB находится по формуле: 

Или     2y -3x +9 = 0 

Пример 14:

Даны вершины треугольника А(8,1), В(0,3), С(-2,-3). Напишите уравнения стороны AB, медианы AD, высоты BE.

Решение от преподавателя:

Обозначим середину стороны BC буквой М. Тогда координаты точки M найдем по формулам деления отрезка пополам. 


M(-1;0) 
Уравнение медианы AM найдем, используя формулу для уравнения прямой, проходящей через две заданные точки. Медиана AМ проходит через точки A(8;1) и М(-1;0), поэтому: 

или 

или 
y = ¹/₉x + ¹/₉ или 9y -x — 1 = 0 
3) Уравнение высоты через вершину B

Пример 15:

Дан треугольник АВС. Найти:

а) величину угла А;

б) уравнение стороны АС;

в) уравнение высоты и медианы, опущенных из вершины В.

Сделать чертеж.

А(-1,2); В(1,3); С(3,-4).

Решение от преподавателя:

Пример 16:

Треугольник задан вершинами А(-6; -2);  В(4; 8); С(2; -8). Найти:

а) уравнение прямой BN, параллельной  стороне АС;

б) уравнение медианы CD;

в) уравнение высоты АЕ;

Решение от преподавателя:

а) уравнение прямой BN, параллельной  стороне АС;

Уравнение прямой AC:

Каноническое уравнение прямой:

или

или
y = ^-3/₄x ^-13/₂ или 4y + 3x +26 = 0

Уравнение BN параллельно AC находится по формуле:
y — y₀ = k(x — x₀)
Подставляя x₀ = 4, k = ^-3/₄, y₀ = 8 получим:
y-8 = ^-3/₄(x-4)
или
y = ^-3/₄x + 11 или 4y + 3x — 44 = 0

б) уравнение медианы CD;

Обозначим середину стороны AB буквой М. Тогда координаты точки M найдем по формулам деления отрезка пополам.


M(-1;3)
Уравнение медианы CM найдем, используя формулу для уравнения прямой, проходящей через две заданные точки. Медиана CМ проходит через точки C(2;-8) и М(-1;3), поэтому:
Каноническое уравнение прямой:

или

или
y = ^-11/₃x ^-2/₃ или 3y + 11x +2 = 0

в) уравнение высоты АЕ;

Прямая, проходящая через точку Е₀(x₀;y₀) и перпендикулярная прямой Ax + By + C = 0 имеет направляющий вектор (A;B) и, значит, представляется уравнениями:

Найдем уравнение высоты через вершину A

y = ^-1/₈x — ¹¹/₄ или 8y +x + 22 = 0

Пример 17:

A(1, 2), В(5, 8), С(11, 3).

Решение от преподавателя:

Пример 18:

В ∆ABC вершины имеют координаты точки А (-3;4), точки В (-4;-3), точки С (8;1).

Составить уравнения стороны (AB), высоты (ВК)  и медианы (CМ).

Решение от преподавателя:

Уравнение прямой AB
Каноническое уравнение прямой:

или

или
x +4 = 0 или x = -4
Уравнение прямой AC
Каноническое уравнение прямой:

или

или
y = ^-1/₄x + 3 или 4y + x — 12 = 0

Найдем уравнение высоты через вершину B

y = 4x + 13 или y -4x — 13 = 0

Уравнение медианы CM найдем, используя формулу для уравнения прямой, проходящей через две заданные точки. Медиана CМ проходит через точки C(8;1) и М(-4;¹/₂), поэтому:
Каноническое уравнение прямой:

или

или
y = ¹/₂₄x + ²/₃ или 24y -x — 16 = 0

Пример 19:

Дан треугольник ABC с координатами вершин A(-5;-3; 2), B(-2;-6;-3) и C(-2; 2;-1).
Найти:
а) длину стороны АВ;
б) косинус угла ABC;
в) площадь треугольника АВС (через векторное произведение).

Решение от преподавателя: