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

Question

[bazeyvit]

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


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

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

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

Answer 1

[yeputons]

Из 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 точку, чтобы максимизировать высоту.

Comments

[gleb_kudr]

А еще, чтобы быть треугольником, три точки не должны лежать на одной прямой. Так что тут простая формула не катит.

[yeputons]

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

Answer 2

[SabMakc]

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

Answer 3

[daeto]

На мой взгляд, эта задача на фильтрацию и поиск максимума/минимума. Очевидно, что такой треугольник (если он не вырожденный) состоит из:

1. Точки на Ox, имеющей минимальную координату по x
2. Точки на Ox, имеющей максимальную координату по x
3. Точки не на Ox, имеющей максимальную по модулю координату по y

Такой поиск делается за один проход по точкам.