Даны 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
Количество треугольников из точек
На плоскости задано множество точек с целочисленными координатами, никакие две из которых не совпадают и никакие три не лежат на одной прямой. Необходимо найти количество треугольников, обладающих следующими свойствами:
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.
Пример правильной и эффективной программы на языке Паскаль
Сколько отрезков можно получить из 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 точку, чтобы максимизировать высоту.