Количество треугольников из точек (6 видео)

Количество треугольников, которые могут быть сформированы с заданными N точек

Даны X и Y координаты N точек на декартовой плоскости. Задача состоит в том, чтобы найти количество возможных треугольников с ненулевой областью, которые можно сформировать, соединяя каждую точку с любой другой точкой.

Примеры:

Эффективный подход : рассмотрите точку Z и найдите ее наклон с любой другой точкой. Теперь, если две точки имеют одинаковый наклон с точкой Z, это означает, что 3 точки коллинеарны и не могут образовывать треугольник. Следовательно, число треугольников, имеющих Z в качестве одной из своих точек, представляет собой количество способов выбора 2 точек из оставшихся точек и затем вычитания количества способов выбора 2 точек из точек, имеющих одинаковый наклон с Z. Поскольку Z может быть любая точка среди N точек, мы должны повторить еще один цикл.

Ниже приведена реализация вышеуказанного подхода:

// C ++ реализация вышеуказанного подхода
#include

using namespace std;

// Эта функция возвращает требуемое число
// из треугольников

int countTriangles(pair int , int > P[], int N)

// Hash Map для хранения частоты

// наклон, соответствующий точке (X, Y)

int , int >, int > mp;

// Перебираем все возможные точки

for ( int i = 0; i

// Рассчитать уклон всех элементов

// с текущим элементом

for ( int j = i + 1; j

int X = P[i].first — P[j].first;

int Y = P[i].second — P[j].second;

// найти наклон с уменьшенным

int g = __gcd(X, Y);

int num = N — (i + 1);

// Общее количество способов сформировать треугольник

// имея одну точку в качестве текущего элемента

ans += (num * (num — 1)) / 2;

// Вычитаем общее количество способов

// формируем треугольник с одинаковым наклоном или

for ( auto j : mp)

ans -= (j.second * (j.second — 1)) / 2;

// Код драйвера для проверки вышеуказанной функции

int N = sizeof (P) / sizeof (P[0]);

# Python3 реализация вышеуказанного подхода

from collections import defaultdict

from math import gcd

# Эта функция возвращает
# необходимое количество треугольников

def countTriangles(P, N):

# Хэш-карта для хранения частоты

# наклон, соответствующий точке (X, Y)

mp = defaultdict( lambda : 0 )

# Итерировать по всем возможным точкам

for i in range ( 0 , N):

# Рассчитать уклон всех элементов

# с текущим элементом

for j in range (i + 1 , N):

# найти склон с пониженным

# Общее количество способов образовать треугольник

# имеющий одну точку в качестве текущего элемента

ans + = (num * (num — 1 )) / / 2

# Вычитая общее количество

# способы сформировать треугольник, имеющий

# того же склона или коллинеарны

ans — = (mp[j] * (mp[j] — 1 )) / / 2

if __name__ = = «__main__» :

P = [[ 0 , 0 ], [ 2 , 0 ], [ 1 , 1 ], [ 2 , 2 ]]

print (countTriangles(P, N))

# Этот код предоставлен Rituraj Jain

Видео:Замечательные точки треугольника | Ботай со мной #030 | Борис Трушин ||Скачать

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

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

1) все вершины треугольника принадлежат заданному множеству;

2) ни одна вершина не лежит на осях координат;

3) треугольник не пересекается с осью Oy, но пересекается с осью Ox.

Напишите эффективную по времени и по используемой памяти программу для решения этой задачи.

Программа считается эффективной по времени, если при увеличении количества точек в k раз время работы возрастает не более чем в k раз. Программа считается эффективной по памяти, если размер памяти для хранения всех необходимых данных не зависит от количества точек и не превышает 1 килобайта.

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

В первой строке задаётся N – количество точек в заданном множестве. Каждая из следующих строк содержит два целых числа x и y – координаты очередной точки. Гарантируется, что 1 ≤ N ≤ 10000, –1000 ≤ x, y ≤ 1000, никакие две точки не совпадают, никакие три не лежат на одной прямой.

Пример входных данных:

Необходимо вывести единственное число: количество удовлетворяющих требованиям треугольников.

Пример выходных данных для приведённого выше примера входных данных:

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

в первой и четвёртой либо во второй и третьей четвертях, причём в одной из этих четвертей должны лежать две вершины, в другой — одна.

Зная количество точек в каждой четверти, можно подсчитать количество искомых треугольников. Например, если в первой четверти лежит n1 точек, а в четвёртой – n4 точек, то количество треугольников, у которых две вершины лежат в первой четверти, а одна — в четвёртой, равно (n1(n1–1)/2) * n4 = n1(n1–1)n4/2.

Если известны величины n1, n2, n3, n4, показывающие количество точек в каждой четверти, то общее количество треугольников равно (n1(n1-1)n4 + n4(n4-1)n1 + n2(n2-1)n3 + n3(n3-1)n2) / 2.

Пример правильной и эффективной программы на языке Паскаль

Видео:#239. ДОКАЗАТЕЛЬСТВО, которое от вас скрывали!Скачать

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

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

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

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

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

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