Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 5.00/6: Рейтинг темы: голосов - 6, средняя оценка - 5.00
0 / 0 / 0
Регистрация: 23.03.2018
Сообщений: 2
1

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

23.03.2018, 09:16. Показов 1193. Ответов 5
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Максимальный треугольник
На плоскости n точек заданы своими координатами (xi,yi) , i=1,2,…,n. Найти треугольник с максимальной площадью с вершинами в заданных точках. Напечатать площадь и номера вершин. Если их несколько, то напечатать любой из них.

input.txt
5
0 0
0 2
1 0.5
0.5 1
2 0

output.txt
2.00
1 2 5

Долго ломаю над этим голову,
результат теста =
2.00
2 3 4
Не могу понять где ошибка.

C++ (Qt)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <iostream>
#include <ctime>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#define use_CRT_SECURE_NO_WARNINGS
#define use_CRT_SECURE_NO_DEPRECATE
#pragma warning(disable : 4996)
using namespace std;
int i, j, k, n, a, b, c, p, s, K, J, I;
double S1 = 0.0,
S2 = 0.0,
S3 = 0.0,
max1 = 0.0,
max2 = 0.0,
max3 = 0.0,
SUPER_MAX = 0.0;
 
int main()
{
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    cin >> n;
 
    double * x = new double[n];
    double * y = new double[n];
 
 
    for (i = 0; i < n; i++)
    {
        cin >> x[i];
        cin >> y[i];
    }
 
    for (i = 1; i < n; i++)
        for (j = i + 1; j < n; j++)
            for (k = j + 1; k < n; k++)
            {
                S1 = abs(((y[k - 1] + y[k])*(x[k] - x[k - 1]) - (y[0] + y[k])*(x[k] - x[0])));
                S2 = abs(((y[j - 1] + y[j])*(x[j] - x[j - 1]) - (y[0] + y[j])*(x[j] - x[0])));
                S3 = abs(((y[i - 1] + y[i])*(x[i] - x[i - 1]) - (y[0] + y[i])*(x[i] - x[0])));
                SUPER_MAX = S1;
                K = k;
                J = j;
                I = i;
                if (S2 > SUPER_MAX)
                {
                    SUPER_MAX = S2;
                    K = k;
                    J = j;
                    I = i;
                }
                else
                    if (S3 > SUPER_MAX)
                    {
                        SUPER_MAX = S3;
                        K = k;
                        J = j;
                        I = i;
                    }
                    else
                    {
                        K = k;
                        J = j;
                        I = i;
                        SUPER_MAX = S1;
                    }
            
 
 
            }
    cout << SUPER_MAX << "." << 0 << 0 << endl << I << ' ' << J << ' ' << K;
}
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
23.03.2018, 09:16
Ответы с готовыми решениями:

Максимальный треугольник
Даны n точек заданные координатами. Требуется найти среди этих точек треугольник с максимальной...

Создать базовый класс Треугольник с 2 наследниками: Равносторонний треугольник, Прямоугольный треугольник
Задание звучит так: Нужно создать базовый класс Треугольник с двумя наследующими его классами - ...

Класс треугольник с произвольным классом - равнобедренный треугольник
Создать класс треугольник, члены класса - длины 3-х сторон. Предусмотреть в классе методы проверки...

Построить треугольник Паскаля. Используя треугольник Паскаля, вычислить 𝑘−ое число Фиббоначчи. Нумерация чисел Фиббона
#include &lt;iostream&gt; using namespace std; int main() { setlocale(LC_ALL, &quot;Russian&quot;); ...

5
192 / 166 / 82
Регистрация: 01.07.2016
Сообщений: 943
23.03.2018, 10:30 2
Проверяй треугольники походу ввода точек. Чтобы образовался треугольник нужно минимум 3 точки, его берём как основной потом после добавление 4 точки могут образоваться три треугольника как нарисовано на картинке. Из 3 треугольников выбираем тот у которого максимальная площадь. Добавляем 5 точку ситуация та же, как и после добавление 4 точки(появляются 3 треугольника).

Думаю так намного легче будет чем возиться с этим бардаком из точек как у вас
Миниатюры
Максимальный треугольник  
0
-1 / 25 / 4
Регистрация: 27.11.2017
Сообщений: 375
23.03.2018, 15:53 3
Цитата Сообщение от no swear Посмотреть сообщение
Проверяй треугольники походу ввода точек. Чтобы образовался треугольник нужно минимум 3 точки, его берём как основной потом после добавление 4 точки могут образоваться три треугольника как нарисовано на картинке. Из 3 треугольников выбираем тот у которого максимальная площадь. Добавляем 5 точку ситуация та же, как и после добавление 4 точки(появляются 3 треугольника).
Нет не такая же. Вполне может быть так, что максимальный треугольник будет образован теми точками, которые Вы удалили на предыдущих шагах, ну хотя бы некоторыми из них.
1
192 / 166 / 82
Регистрация: 01.07.2016
Сообщений: 943
23.03.2018, 19:49 4
Цитата Сообщение от Просто Саша Посмотреть сообщение
Вполне может быть так, что максимальный треугольник будет образован теми точками, которые Вы удалили на предыдущих шагах
Не подумал об этом. Спасибо что исправили меня.

Всё что я могу посоветовать так это использовать тип данных std :: pair<T1, T2>. Для данной задачи кстати очень подойдёт.
0
192 / 166 / 82
Регистрация: 01.07.2016
Сообщений: 943
23.03.2018, 20:06 5
Треугольник x[3] y[3], x[4] y[4], x[2] y[2] выбрали как максимальный, про точку x[1] y[1] "забываем". Добавили точку x[5] y[5] получаем новые треугольники с точками
x[2] y[2], x[4] y[4], x[5] y[5] - 1 треугольник
x[3] y[3], x[4] y[4], x[5] y[5] - 2 треугольник
x[3] y[3], x[5] y[5], x[2] y[2] - 3 треугольник
Из них никакой максимальным не выйдет так как в самом деле максимальным треугольником будет треугольник с точками x[1] y[1], x[5] y[5], x[3] y[3].

Что то типа такого может произойти если следовать моему алгоритму
Миниатюры
Максимальный треугольник  
0
Диссидент
Эксперт C
27706 / 17322 / 3812
Регистрация: 24.12.2010
Сообщений: 38,979
23.03.2018, 21:14 6
И правда трудновато разобраться в этом бардаке... Имхо, все просто.
kiesik98, ну, ввели точки (строки 29-33). Организовали цикл перебора (стр.35-38). Не совсем правильно.
C++
1
2
3
for (i = 0; i < n-2; i++)
        for (j = i + 1; j < n-1; j++)
            for (k = j + 1; k < n; k++) {
А внутри цикла надо просто посчитать площадь треугольника. ОДНОГО. И сравнить его с максимально-достигнутым. Если он больше - запомнить его площадь и номера точек. ВСЕ!
0
23.03.2018, 21:14
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
23.03.2018, 21:14
Помогаю со студенческими работами здесь

Создать абстрактный класс "Треугольник" и производный - "Равнобедренный треугольник"
Задание Создать абстрактный класс треугольник. Предусмотреть в классе методы проверки...

В Paintbox вписать в круг треугольник, потом квадрат, и равнобедренный треугольник
Int a=StrToInt (Edit1-&gt;Text); PaintBox-&gt;Canvas-&gt;Ellipse(200-a/2,200-a/2,200+a/2,200+a/2);нарисовал...

Треугольник задан координатами вершин х 1 у1 х 2 у 2 х 3 у 3 точка а задана координатами х у требуется написать программу определяющую попадает ли указанная точка в заданный треугольник
Треугольник задан координатами вершин х 1 у1 х 2 у 2 х 3 у 3 точка а задана координатами х у...

Выбрать максимальный по площади треугольник из трех, заданных своими сторонами...
Всем доброго времени суток! Выбрать максимальный по площади треугольник из трех, заданных ...

Построить треугольник с заданными координатами вершин. Треугольник должен медленно падать вниз.
Построить треугольник с координатами вершин: А (0,0), В (80, 0), С (0, 100). Треугольник должен...

Треугольник задан длинами сторон A,B,C. Разработать схему алгоритма,определяющую,существует ли данный треугольник
Треугольник задан длинами сторон A,B,C. Разработать схему алгоритма,определяющую,существует ли...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
6
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru