Question

Для скольких точек плоскости выполняется правило треугольника*

Answer 1

БЛИН Я ПЕРЕПУТАЛ ОКЗЫАВЕТСЯ 3 ТОЧКИ ВВВОТ

Answer 2

Для 3 точек, т.к треугольник имеет 3 угла. Логично же

Answer 3

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

Пусть на плоскости задано n точек, обозначим количество возможных троек точек из этих n точек за C(n,3) - это сочетание из n по 3. Тогда каждая такая тройка точек может образовать треугольник, если расстояние между каждой парой точек в этой тройке меньше, чем сумма расстояний между каждой из этих точек и любой из оставшихся n-3 точек.

Таким образом, для каждой тройки точек, мы можем проверить выполнение правила треугольника за O(1) операций, и следовательно, для n точек в плоскости правило треугольника выполняется для C(n,3) троек точек.

Таким образом, для n точек на плоскости правило треугольника выполняется для C(n,3) троек точек, где C(n,3) = n(n-1)(n-2)/6.