Количество треугольников на плоскости

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

Примеры:

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

// C ++ программа для поиска номера
// треугольники на плоскости, если не больше
// тогда две точки коллинеарны.
#include

using namespace std;

// Функция для определения количества треугольников
// в плоскости.

int countNumberOfTriangles( int n)

// Формула для определения количества треугольников

// nC3 = n * (n — 1) * (n — 2) / 6

return n * (n — 1) * (n — 2) / 6;

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

// Функция для определения количества треугольников

static int countNumberOfTriangles( int n)

// Формула для поиска номера треугольника

// nC3 = n * (n — 1) * (n — 2) / 6

return n * (n — 1 ) * (n — 2 ) / 6 ;

public static void main(String[] args)

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

# Функция для поиска номера
# треугольников в плоскости.

# Формула для поиска

if __name__ = = ‘__main__’ :

# Этот код добавлен
# от ajit

// C # программа для поиска
// количество треугольников в
// плоскость, если не более
// две точки коллинеарны.

// Функция для поиска номера

// треугольников на плоскости.

static int countNumberOfTriangles( int n)

// Формула для поиска номера

public static void Main()

// Этот код предоставлен anuj_67.

// PHP программа для поиска
// количество треугольников в
// плоскость, если не более
// две точки коллинеарны.

// Функция для поиска номера
// треугольников на плоскости.

function countNumberOfTriangles( $n )

// Формула для поиска номера

// треугольников nC3 = n *

return $n * ( $n — 1) *

echo countNumberOfTriangles( $n );

// Этот код добавлен
// от anuj_67.
?>

Сколько отрезков можно получить из N точек? Сколько различных треугольников можно получить из N отрезков?

Есть ли какие-то формулы, в которые можно поставить число N и получить ответ?

Все это мне необходимо для решения этой задачи:

На плоскости дан набор точек с целочисленными координатами. Необходимо найти треугольник наибольшей площади с вершинами в этих точках, одна сторона которого лежит на оси Ох. Если таких треугольников нет, то вывести «таких нет»

• Вопрос задан более трёх лет назад
• 15620 просмотров

Из N точек можно получить N*(N-1)/2 различных пар (C из N по 2) Длины, возможно, будут разные, но это уже без знания конкретных точек не лечится.

Про треугольники аналогичная ситуация, но надо выбрать три отрезка — M*(M-1)*(M-2)/6, где M — количество отрезков. Если же надо просто количество треугольников из заданных точек, то их будет N*(N-1)*(N-2)/6.

Получается из соображений выбираем первую точку N способами, вторую — N-1, третью — N-2 (потому что предыдущие уже выбраны). Надо разделить на 6=3!, потому что каждую перестановку трёх точек получили ровно по разу.

Не очень понимаю, как это может в данной конкретной задаче.
Но точно поможет такое наблюдение: S=len*h/2, где len — длина основания, h — соответствующая высота. Т.к. основание лежит на Ox, надо найти длиннейший отрезок на этой оси (max-min) и самую далёкую от Ox точку, чтобы максимизировать высоту.

Подсчет комбинаторных объектов (стр. 2 )

Из за большого объема этот материал размещен на нескольких страницах: 1 2 3 4 5

УКАЗАНИЯ И РЕШЕНИЯ

1. Точка. Прямая. Плоскость. Пространство. Если все n точек на прямой разные, то они разобьют прямую на points(n) = n + 1 = + частей.

Пусть lines(n) – количество частей, на которое разбивают плоскость n прямых. n — ая прямая разобьет плоскость на максимальное количество частей, если она пересечется со всеми n – 1 предыдущими прямыми, которые разбивают плоскость на lines(n – 1) частей. То есть n — ая прямая должна пройти по n частям плоскости, каждая из которых будет поделена пополам. Но эти n частей плоскости и являются количеством частей прямой, на которое ее делят n – 1 точка. Имеем:

lines(n) = + +

прямые на плоскости

Обозначим через planes(n) количество частей, на которое разбивают пространство n плоскостей. Заметим, что количество новых трехмерных областей, образованных новым сечением, равно количеству двумерных областей, образованных на новой плоскости линиями его пересечения с предыдущими плоскостями. То есть

planes(n) = + + +

2. Окружность. Эллипс. Треугольник. Пусть n фигур разбивают плоскость на f(n) частей. Одна фигура разбивает плоскость на две части. Каждая следующая n — ая фигура должна иметь максимально возможное число пересечений k с каждой из (n – 1) предыдущих фигур. Две окружности могут пересекаться максимум в двух точках (k = 2), два эллипса в четырех (k = 4), а два треугольника в шести (k = 6). Тогда

Решим рекуррентное уравнение:

f(n) = k * ((n – 1) + (n – 2) + … + 1) + 2 == k * + 2

Заметим, что f(0) = 1 для любого k (ноль фигур делят плоскость на одну часть).

окружности на плоскости

эллипсы на плоскости

n = 1 n = 2 n = 3

треугольники на плоскости

3. Прямые и окружность. Количество частей, на которое n прямых делят окружность, равно количеству частей, на которое n прямых делят плоскость (задача 1).

прямые на окружности

4. Плоскости и куб. Количество частей, на которое n плоскостей делят куб, равно количеству частей, на которое n плоскостей делят пространство (задача 1).

5. Хорды на окружности. Теорема. Проведем в замкнутой связной фигуре d отрезков, которые соединяют точки на границе и находятся полностью внутри фигуры. Допустим, что они пересекаются между собой в t точках. Тогда количество частей, на которое поделят отрезки внутреннюю область фигуры, равно d + t + 1.

Доказательство по индукции. Если не проведено ни одного отрезка (d = 0, t = 0), то фигура содержит одну внутреннюю область. Пусть при проведении очередного отрезка появится k новых точек пересечения. Тогда этот отрезок пройдет по k + 1 внутренней области фигуры, разбивая каждую из них пополам. Таким образом количество областей увеличится на k + 1 (k новых точек пересечения плюс один отрезок).

Окружность является замкнутой связной фигурой. Проведем все хорды, которые соединяют n точек. Поскольку каждые две точки образуют хорду, то количество проведенных хорд равно . Через каждые четыре точки на окружности можно провести только две пересекающиеся хорды. Количество точек пересечения хорд равно . Таким образом количество областей, на которое поделят хорды окружность, равно 1 + + .

хорды на окружности

6. Треугольники в многоугольнике. Каждый из образованных треугольников может иметь 0, 1, 2 или 3 общие вершины с многоугольником:

a) 0 общих вершин б)1 общая вершина в)2 общие вершины г) 3 общие вершины

Каждый треугольник, который не имеет общих вершин с многоугольником, образуется тремя диагоналями, которые в свою очередь определяются 6 точками (а). Количество таких треугольников равно . Треугольники, лишь одна вершина которых совпадает с вершиной многоугольника (б), образуются пятью точками, любая из которых может быть вершиной. Таких треугольников 5 * . Треугольники, две вершины которых лежат в вершинах многоугольника, определяются 4 точками (в). При этом каждые 4 точки образуют 4 разные треугольника. Их общее число равно 4 * . Количество треугольников, все вершины которых лежат в вершинах многоугольника (г), равно . Таким образом, общее количество треугольников равно

f(n) = + 5 * + 4 * +

Например, количество треугольников в пятиугольнике со всеми проведенными диагоналями равно + 5 * + 4 * + = 0 + 5 + 20 + 10 = 35.

Треугольники в пятиугольнике

7. Подсчитать деревья [Вальядолид, 10007]. Количество неразмеченных бинарных деревьев с n вершинами равно числам Каталана

Вершинам каждого неразмеченного дерева можно поставить в соответствие метки n! способами. Таким образом, число искомых размеченных корневых бинарных деревьев равно

f(n) = * n! = = = (n + 2) * (n + 3) * … * (2n)

Для вычисления результата достаточно перемножить все числа от n + 2 до 2n. Поскольку n £ 300, то следует использовать класс длинной арифметики BigInteger.

Реализация. Количество тестов может быть большим, а n £ 300. Вычислим все значения f(n) и сохраним их в массиве res[MAX]. Вычислим значения f(i) и занесем их в ячейки res[i], i = 1, 2, …, 300. Для каждого входного n выводим res[n].