Как найти треугольник максимальной

Как найти треугольник максимальной

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

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

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

Описание входных данных

В первой строке вводится одно целое положительное число — количество точек N.

Каждая из следующих N строк содержит два целых числа — сначала координата х, затем координата у очередной точки. Числа разделены пробелом.

Описание выходных данных

Программа должна вывести одно число – максимальную площадь треугольника, удовлетворяющего условиям задачи. Если такого треугольника не существует, программа должна вывести ноль.

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

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

Заметим, что раз искомый треугольник не должен иметь общих точек с осью ОХ, то все его вершины будут одновременно или ниже оси, или выше. Тогда найдём треугольник с максимальной площадью для верхней полуплоскости, для нижней, а потом выберем лучший из них.

Задачи для обеих полуплоскостей решаются аналогично, рассмотрим решение для положительной полуплоскости. Так как две точки будут лежать на оси ОУ, удобнее всего будет считать площадь треугольника по формуле S = a · h / 2, где a — длина основания треугольника, лежащего на оси ОУ, а h — длина перпендикуляра из третьей точки на ось ОУ.

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

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

Ниже приведён код решения на языке Pascal версии 2.6.2.

var n, i, x, y, maxPosY, minPosY, maxNegY, minNegY, maxNegAbsX, maxPosAbsX, s : longint;

Максимальный периметр треугольника из массива

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

Примеры :

Наивное решение:
Решение по грубой силе: проверить для всех комбинаций из 3 элементов, образует ли он треугольник или нет, и обновить максимальный периметр, если он образует треугольник. Сложность наивного решения составляет O (n 3 ). Ниже приведен код для этого.

// Решение грубой силы, чтобы найти
// вне максимального периметра треугольника, который
// может быть сформирован с использованием элементов
// данного массива
#include
#include

using namespace std;

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

void maxPerimeter( int arr[], int n)<

// инициализируем максимальный периметр

// подбираем 3 разных элемента

for ( int i = 0; i

for ( int j = i + 1; j

for ( int k = j + 1; k

// a, b, c – 3 стороны треугольника

// проверяем, формируются ли a, b, c

// треугольник или нет.

// если он образует треугольник

// затем обновляем максимальное значение.

maxi = max(maxi, a+b+c);

// Если максимальный периметр ненулевой

// затем распечатать его.

if (maxi) cout “Maximum Perimeter is: “

// иначе треугольник не образуется

else cout “Triangle formation “

“is not possible.”

// Программа для водителя

// тестовый пример 1

// контрольный пример 2

// тестовый пример 3

// Решение грубой силы, чтобы узнать максимум
// треугольник периметра, который может быть сформирован
// используя элементы данного массива

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

static void maxPerimeter( int arr[], int n)

// инициализируем максимальный периметр как 0.

// подбираем 3 разных элемента

for ( int i = 0 ; i 2 ; i++)

for ( int j = i + 1 ; j 1 ; j++)

for ( int k = j + 1 ; k

// a, b, c – 3 стороны

// проверяем, a, b, c

// образует треугольник или нет.

// если он образует треугольник

// затем обновляем максимум

maxi = Math.max(maxi, a+b+c);

// Если максимальный периметр ненулевой

// затем распечатать его.

System.out.println( “Maximum Perimeter is: “

// иначе треугольник не образуется

System.out.println( “Triangle formation “

+ “is not possible.” );

// Программа для водителя

public static void main (String[] args)

// тестовый пример 1

// контрольный пример 2

// тестовый пример 3

12 , 5 , 55 , 4 , 9 >;

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

# Решение грубой силы, чтобы найти
№ из максимального периметра треугольника
# который может быть сформирован с использованием
# элементы данного массива

# Функция, чтобы узнать
# максимальный периметр

# подобрать 3 разных

# элементы из массива.

for i in range (n – 2 ):

for j in range (i + 1 , n – 1 ):

for k in range (j + 1 , n):

# a, b, c – 3 стороны

if (a + c and b + c

maxi = max (maxi, a + b + c)

return “Triangle formation is not possible”

return “Maximum Perimeter is: ” + str (maxi)

arr1 = [ 6 , 1 , 6 , 5 , 8 , 4 ]

arr2 = [ 2 , 20 , 7 , 55 ,

arr3 = [ 33 , 6 , 20 , 1 , 8 ,

12 , 5 , 55 , 4 , 9 ]

if __name__ = = ‘__main__’ :

# Этот код добавлен
# Прита Updhayay

// Решение грубой силы, чтобы узнать
// максимальный периметр треугольника, который
// может быть сформирован с использованием элементов
// данного массива

// Функция, чтобы узнать

static void maxPerimeter( int []arr,

// подбираем 3 разных элемента

for ( int i = 0; i

for ( int j = i + 1; j

for ( int k = j + 1; k

// a, b, c – 3 стороны

// проверяем, a, b, c

// образует треугольник или нет.

// если он образует треугольник

// затем обновляем максимум

maxi = Math.Max(maxi, a + b + c);

// Если максимальный периметр

// не ноль, затем распечатать его.

Console.WriteLine( “Maximum Perimeter is: ” + maxi);

// иначе треугольника нет

Console.WriteLine( “Triangle formation ” +

“is not possible.” );

public static void Main ()

// тестовый пример 1

// контрольный пример 2

// тестовый пример 3

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

// Решение грубой силы, чтобы найти
// вне максимального периметра треугольника, который
// может быть сформирован с использованием элементов
// данного массива

// Функция, чтобы узнать
// максимальный периметр

function maxPerimeter( $arr , $n )

// подбираем 3 разных

// элементы из массива.

for ( $i = 0; $i $n – 2; $i ++)

for ( $j = $i + 1; $j $n – 1; $j ++)

for ( $k = $j + 1; $k $n ; $k ++)

// a, b, c – 3 стороны

// проверяем, a, b, c

// образует треугольник или нет.

// если он образует треугольник

// затем обновляем максимальное значение.

$maxi = max( $maxi , $a + $b + $c );

// Если максимальный периметр

// не ноль, затем распечатать его.

echo “Maximum Perimeter is: ” ;

// иначе треугольника нет

echo “Triangle formation ” ;

echo “is not possible. n” ;

// тестовый пример 1

$arr1 = array (6, 1, 6, 5, 8, 4);

maxPerimeter( $arr1 , 6);

// контрольный пример 2

$arr2 = array (2, 20, 7, 55,

maxPerimeter( $arr2 , 8);

// тестовый пример 3

$arr3 = array (33, 6, 20, 1, 8,

maxPerimeter( $arr3 , 10);

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

Выход :

Эффективный подход:
Сначала мы можем отсортировать массив по возрастанию. Итак, первый элемент будет максимальным, а последний будет минимальным. Теперь, если первые 3 элемента этого отсортированного массива образуют треугольник, это будет треугольник с максимальным периметром, так как для всех других комбинаций сумма элементов (то есть периметр этого треугольника) будет = b> = c). a, b, c не могут образовывать треугольник, поэтому a> = b + c. As, b и c = c + d (если мы отбросим b и возьмем d) или a> = b + d (если мы отбросим c и возьмем d). Итак, мы должны бросить и забрать д.
Опять же набор анализа для b, c и d. Мы можем продолжать это до последнего и всякий раз, когда мы находим треугольник, образующий тройку, мы можем прекратить проверку, так как эта тройка дает максимальный периметр.
Следовательно, если в отсортированном массиве arr [i] Ниже приведена простая реализация этой концепции:

// Эффективное решение для поиска
// вне максимального периметра треугольника, который
// может быть сформирован с использованием элементов
// данного массива
#include
#include

using namespace std;

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

void maxPerimeter( int arr[], int n)<

// сортируем элементы массива

// в обратном порядке

sort(arr, arr+n, greater int >());

// цикл через отсортированный массив

// и проверяем, образует ли он

// треугольник или нет.

for ( int i = 0; i

// Проверяем, есть ли arr [i], arr [i + 1]

// и arr [i + 2] образует треугольник

// если он образует треугольник

// это треугольник с

maxi = max(maxi, arr[i] + arr[i+1] + arr[i+2]);

// Если максимальный периметр ненулевой

// затем распечатать его.

cout “Maximum Perimeter is: “

// иначе треугольник не образуется

cout “Triangle formation”

“is not possible.”

// Программа для водителя

// тестовый пример 1

// контрольный пример 2

// тестовый пример 3

// Эффективное решение для поиска
// вне максимального периметра треугольника, который
// может быть сформирован с использованием элементов
// данного массива

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

static void maxPerimeter( int arr[], int n) <

// сортируем элементы массива

// в обратном порядке

// сортировать (arr, arr + n, больше ());

// цикл через отсортированный массив

// и проверяем, образует ли он

// треугольник или нет.

for ( int i = 0 ; i 2 ; i++) <

// Проверяем, есть ли arr [i], arr [i + 1]

// и arr [i + 2] образует треугольник

if (arr[i] 1 ] + arr[i + 2 ]) <

// если он образует треугольник

// это треугольник с

maxi = Math.max(maxi, arr[i] + arr[i + 1 ] + arr[i + 2 ]);

// Если максимальный периметр ненулевой

// затем распечатать его.

System.out.println( “Maximum Perimeter is: ” + maxi);

> // иначе треугольник не образуется

System.out.println( “Triangle formation is not possible.” );

// Функция возвращает отсортированный массив по убыванию

static int [] arrRevSort( int [] arr) <

Arrays.sort(arr, 0 , arr.length);

int j = arr.length – 1 ;

for ( int i = 0 ; i 2 ; i++, j–) <

// Программа для водителя

public static void main(String[] args) <

// тестовый пример 1

// контрольный пример 2

// тестовый пример 3

>
/ * Этот Java-код предоставлен 29AjayKumar * /

# Эффективное решение, чтобы найти
№ из максимального периметра треугольника, который
# может быть сформирован с использованием элементов
# данного массива

# Функция для поиска
# максимальный периметр

for i in range ( 0 , n – 2 ):

if arr[i] + 1 ] + arr[i + 2 ]):

maxi = max (maxi, arr[i] +

arr[i + 1 ] + arr[i + 2 ])

return “Triangle formation is not possible”

return “Maximum Perimeter is: ” + str (maxi)

arr1 = [ 6 , 1 , 6 , 5 , 8 , 4 ]

arr2 = [ 2 , 20 , 7 , 55 ,

arr3 = [ 33 , 6 , 20 , 1 , 8 ,

12 , 5 , 55 , 4 , 9 ]

if __name__ = = ‘__main__’ :

# Этот код добавлен
# Прита Упадхяй

// Эффективное решение для поиска
// вне максимального периметра треугольника, который
// может быть сформирован с использованием элементов
// данного массива

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

static void maxPerimeter( int [] arr, int n) <

// сортируем элементы массива

// в обратном порядке

// сортировать (arr, arr + n, больше ());

// цикл через отсортированный массив

// и проверяем, образует ли он

// треугольник или нет.

for ( int i = 0; i

// Проверяем, есть ли arr [i], arr [i + 1]

// и arr [i + 2] образует треугольник

// если он образует треугольник

// это треугольник с

maxi = Math.Max(maxi, arr[i] + arr[i + 1] + arr[i + 2]);

// Если максимальный периметр ненулевой

// затем распечатать его.

Console.WriteLine( “Maximum Perimeter is: ” + maxi);

> // иначе треугольник не образуется

Console.WriteLine( “Triangle formation is not possible.” );

// Функция возвращает отсортированный массив по убыванию

static int [] arrRevSort( int [] arr) <

int j = arr.Length – 1;

for ( int i = 0; i

// Программа для водителя

public static void Main() <

// тестовый пример 1

// контрольный пример 2

// тестовый пример 3

>
/ * Этот код Java предоставлен mits * /

// Эффективное решение, чтобы узнать максимум
// треугольник периметра, который может быть сформирован
// используя элементы данного массива

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

function maxPerimeter(& $arr , $n )

// сортируем элементы массива в

// инициализируем максимальный периметр до 0

// цикл через отсортированный массив

// и проверяем, образует ли он

// треугольник или нет.

for ( $i = 0; $i $n – 2; $i ++)

// Проверяем, есть ли arr [i], arr [i + 1]

// и arr [i + 2] образует треугольник

if ( $arr [ $i ] $arr [ $i + 1] +

// если он образует треугольник

// это треугольник с

$maxi = max( $maxi , $arr [ $i ] +

// Если максимальный периметр ненулевой

// затем распечатать его.

echo ( “Maximum Perimeter is: ” );

// иначе треугольник не образуется

echo ( “Triangle formation ” );

echo ( “is not possible.” );

// тестовый пример 1

$arr1 = array (6, 1, 6, 5, 8, 4);

maxPerimeter( $arr1 , $s );

// контрольный пример 2

$arr2 = array (2, 20, 7, 55, 1,33, 12, 4);

$st = sizeof( $arr2 );

maxPerimeter( $arr2 , $st );

// тестовый пример 3

$arr3 = array (33, 6, 20, 1, 8,

$st1 = sizeof( $arr3 );

maxPerimeter( $arr3 , $st1 );

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

Выход :

Временная сложность такого подхода составляет O (n * log (n)). Это много времени требуется для сортировки массива.

Найдите максимальное количество треугольников. Интернет пользователи в тупике

На первый взгляд, это достаточно простая задачка. Автор этой математической задачи, опубликовал её в интернете под ником @thomas_violence .

Эта задачка вызвала много разногласий среди пользователей. Посыпались комментарии. Люди спорили и доказывали.

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

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

Люди часто забывают, что на вид простые тесты, скрывают в себе маленькие секреты.

Итак, вы готовы к подсчёту? Поехали….

Ну как, справились? Какой результат вы получили? Поделитесь в комментариях

А вот и правильный ответ.

Всего здесь 18 треугольников!

Надеемся, вам понравилась эта задачка и вы смогли проверить свои знания и внимательность.

[spoiler title=”источники:”]

http://fun-gate.ru/%D1%82%D0%B5%D1%81%D1%82%D1%8B/%D0%BD%D0%B0%D0%B9%D0%B4%D0%B8%D1%82%D0%B5-%D0%BC%D0%B0%D0%BA%D1%81%D0%B8%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D0%BE%D0%B5-%D0%BA%D0%BE%D0%BB%D0%B8%D1%87%D0%B5%D1%81%D1%82%D0%B2%D0%BE-%D1%82%D1%80%D0%B5/

[/spoiler]

Макеты страниц

Given an array of non-negative integers. Find out three elements from this array that form a triangle of the maximum perimeter.

Examples:  

Input : {6, 1, 6, 5, 8, 4}
Output : 20

Input : {2, 20, 7, 55, 1, 33, 12, 4}
Output : Triangle formation is not possible.

Input: {33, 6, 20, 1, 8, 12, 5, 55, 4, 9}
Output: 41 

Naive Solution: The brute force solution is: check for all combinations of 3 elements, whether it forms a triangle or not, and update the maximum perimeter if it forms a triangle. The complexity of the naive solution is O(n³). Below is the code for it. 

Implementation:

Maximum Perimeter is: 20
Triangle formation is not possible.
Maximum Perimeter is: 41

Auxiliary Space : O(1) 

Efficient Approach: 

First, we can sort the array in non-increasing order. So, the first element will be the maximum and the last will be the minimum. Now if the first 3 elements of this sorted array form a triangle, then it will be the maximum perimeter triangle, as for all other combinations the sum of elements(i.e. the perimeter of that triangle) will be = b >= c). a, b,c can not form a triangle, so a >= b + c. As, b and c = c+d (if we drop b and take d) or a >= b+d (if we drop c and take d). So, we have to drop a and pick up d. 

Again, the same set of analysis for b, c, and d. We can continue this till end and whenever we find a triangle forming a triple, then we can stop checking, as this triple gives a maximum perimeter. 

Hence, if arr[i] < arr[i+1] + arr[i+2] (0 <= i <= n-3)in the sorted array, then arr[i], arr[i+1] and arr[i+2] form a triangle. 

Below is the simple implementation of this concept: 

Maximum Perimeter is: 20
Triangle formationis not possible.
Maximum Perimeter is: 41

Complexity Analysis:

• Time complexity: O(n*log(n)). This much time is required to sort the array.
• Space complexity: O(1) since constant space is used.

Last Updated :
03 Jan, 2023

Like Article

Save Article

Даётся множество точек и надо найти треугольник с самым большим периметром (с вершинами в этих точках).
Входные данные: 2<n<101,
x и y не больше 10000

#include <iostream>
#include <math.h>

using namespace std;

struct Point
{
    int x;
    int y;
};

int main()
{
    int n; 
    double max = 0;
    cin >> n; //Вводим к-во точек
    Point *g = new Point[n];
    for (int i = 0; i < n; i++)
    {
        cin >> g[i].x >> g[i].y; //Вводим координаты каждой точки
    }
    for (int i = 0; i < n - 2; i++)
    {
        for (int h = 1 + i; h < n - 1; h++)
        {
            for (int j = 1 + h; j < n; j++)
            {
                double a = sqrt(pow(g[i].x - g[h].x, 2) + pow(g[i].y - g[h].y, 2)), b = sqrt(pow(g[i].x - g[j].x, 2) + pow(g[i].y - g[j].y, 2)), c = sqrt(pow(g[j].x - g[h].x, 2) + pow(g[j].y - g[h].y, 2)); //Считаем каждую сторону треугольника
                if (a + b > c && a + c > b && b + c > a) //Проверяем возможность существования такого треугольника
                {
                    double p = a + b + c;
                    if (p > max) //Находим максимальный периметр
                        max = p;
                }
            }
        }
    }
    cout << max;
    return 0;
}

Оно проходит 19 тестов и стопорится. Скорее всего из-за времени. Как оптимизировать код?