2 / 2 / 1
Регистрация: 30.10.2014
Сообщений: 31
1

Из заданных точек найти вершины треугольника, который будет иметь наибольшую площадь

26.01.2016, 14:48. Показов 1865. Ответов 14
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
На плоскости даны 1000 точек. Найти треугольник, который будет иметь наибольшую площадь и вывести на экран и треугольник и точки. Координаты выбираются случайным образом. Точки, лежащие внутри треугольника, рисуются синим цветом, а лежащие снаружи – красным.
До рисования еще не дошел, но вот наброски. Пытаюсь искать наибольший периметр для всех треугольников.
Я запутался и действительно нужна помощь. Может кто-нибудь идею дать или помочь?

C++
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
 
#include <iostream>
#include <math.h>
#include <cstdio>
#include <cstdlib>
#include <ctime>
 
using namespace std;
 
int main()
{
    srand(time(NULL));
    setlocale(0, "");
 
    int n = 0, u = 0;
 
    cout << "Введите n: ";
    cin >> n;
 
    int *x = new int[n];
    int *y = new int[n];
    float *p = new float[u];
 
    for (int i = 0; i < n; i++)
    {
        x[i] = rand() % 10;
        y[i] = rand() % 10;
 
        cout << "(" << x[i] << ", " << y[i] << ")" << endl;
    }
 
    cout << endl;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            for (int k = 0; k < n; k++)
            {
                if (k != j || k != i || j != i)
                {
                    u++;
                    p[u] = sqrt(pow(x[i] - y[i], 2) + pow(x[j] - y[j], 2) + pow(x[k] - y[k], 2));
                    cout << p[u] << endl;
                }
            }
        }
    }
 
    system("pause");
    return 0;
}
 Комментарий модератора 
Ознакомьтесь с правилами форума
5.5 Запрещено размещать тему в нескольких подразделах одного раздела одновременно (кросспостинг), а также дублировать тему в одном разделе.
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
26.01.2016, 14:48
Ответы с готовыми решениями:

Найти треугольник, который будет иметь наибольшую площадь и вывести на экран
Задача: На плоскости даны 1000 точек. Найти треугольник, который будет иметь наибольшую площадь и...

При каком радиусе полукруга сечение канала будет иметь наибольшую площадь?
Очень нужна помощь, надеюсь на то, что добрые люди помогут с решением. Из-за болезни пропустил...

Определить размеры катетов, при которых треугольник будет иметь наибольшую площадь
В прямоугольном треугольнике задана длина гипотенузы. Определить размеры катетов, при которых...

Найти минимальный радиус шара, который будет охватывать все заданные точки(центр окружности лежит на одной из заданных точек)
есть программа, проблема в передаче массива в функцию a #include &quot;stdio.h&quot; #include &quot;conio.h&quot;...

14
543 / 486 / 104
Регистрация: 05.05.2014
Сообщений: 1,110
26.01.2016, 17:07 2
C++
1
2
3
4
5
6
7
8
9
10
11
for (int i = 0; i < n-2; i++)   {
        for (int j = i+1; j < n-1; j++)
        {
            for (int k = j+1; k < n; k++)
            {
                    u++;
                    p[u] = sqrt(pow(x[i] - y[i], 2) + pow(x[j] - y[j], 2) + pow(x[k] - y[k], 2));
                    cout << p[u] << endl;
            }
        }
}
0
2923 / 844 / 324
Регистрация: 30.04.2009
Сообщений: 2,633
26.01.2016, 18:39 3
1. Задача не в том разделе форума.
2. Исходя из того, что дано 1000 точек, простой поиск площадей всех треугольников не совсем разумное решение
0
2657 / 2232 / 240
Регистрация: 03.07.2012
Сообщений: 8,128
Записей в блоге: 1
26.01.2016, 20:15 4
Странно - требуется наибольшая площадь, а ТС ищет наибольший периметр. Для 1000 точек можно тупо перебрать все возможные треугольники и найти наибольшую площадь.
0
543 / 486 / 104
Регистрация: 05.05.2014
Сообщений: 1,110
26.01.2016, 20:19 5
Цитата Сообщение от zer0mail Посмотреть сообщение
требуется наибольшая площадь, а ТС ищет наибольший периметр
Ну, наверное дальше хочет воспользоваться формулой Герона. Хотя, конечно, через векторные произведения проще
0
2657 / 2232 / 240
Регистрация: 03.07.2012
Сообщений: 8,128
Записей в блоге: 1
26.01.2016, 20:27 6
А смысл? Треугольник с наибольшей площадью может не иметь наибольший периметр.
0
543 / 486 / 104
Регистрация: 05.05.2014
Сообщений: 1,110
26.01.2016, 20:31 7
Цитата Сообщение от zer0mail Посмотреть сообщение
А смысл?
Ну, видно, что программа еще не доделана. ТС находится в поиске. Может быть, он планирует через периметр и стороны подсчитать площадь, а может быть вообще бросить это занятие
Имхо, не очень много смысла искать смысл в его коде на этом этапе...
0
2 / 2 / 1
Регистрация: 30.10.2014
Сообщений: 31
26.01.2016, 20:36  [ТС] 8
8-BITOV, про векторное произведение можно поподробнее, раз уже сказали?)
0
2657 / 2232 / 240
Регистрация: 03.07.2012
Сообщений: 8,128
Записей в блоге: 1
26.01.2016, 21:03 9
Векторное произведение векторов А и В = AxB= [A,B]=Ax*By-Ay*Bx=+- 2*Площадь треугольника, натянутого на А и В.
Т.е. векторное произведение может быть отрицательным, но его абсолютное значение=удвоенной площади.
Для треугольника A=X-Z, B=Y-Z, где X,Y,Z - вектора вершин.

Вообще-то это школьная математика...
2
543 / 486 / 104
Регистрация: 05.05.2014
Сообщений: 1,110
26.01.2016, 23:23 10
mamzel, Ну вот, вам все уже рассказали...
0
2 / 2 / 1
Регистрация: 30.10.2014
Сообщений: 31
27.01.2016, 19:47  [ТС] 11
Треугольник я нашел. Как все невостребованные точки, лежащие внутри треугольника, зарисовать синим цветом.
0
Диссидент
Эксперт C
27697 / 17314 / 3811
Регистрация: 24.12.2010
Сообщений: 38,979
27.01.2016, 19:53 12
Зарисуешь сам. Видимо, вопрос в том, как их найти?
0
2 / 2 / 1
Регистрация: 30.10.2014
Сообщений: 31
27.01.2016, 19:55  [ТС] 13
Байт, да, как их найти(
0
Диссидент
Эксперт C
27697 / 17314 / 3811
Регистрация: 24.12.2010
Сообщений: 38,979
27.01.2016, 20:03 14
Цитата Сообщение от mamzel Посмотреть сообщение
как их найти
Подсказка из аналитической геометрии. Если провести прямую (написать ее уравнение в виде Ax+By+С=0), то все точки, лежащие по одну ее сторону при подстановке в уравнение дают один знак, по другую другой. (Точки, лежащие на прямой, естественно, знака не дают, т.к. дают 0)
Отсюда. Точка лежит внутри треугольника тогда и только тогда, когда при подставлении ее координат в уравнение каждой стороны она дает тот же знак, что и противолежащая вершина.
Подсказка для начинающих программистов:
числа a,b имеют один знак тогда и только тогда, когда a*b > 0
1
2 / 2 / 1
Регистрация: 30.10.2014
Сообщений: 31
28.01.2016, 09:20  [ТС] 15
Если кому интересно, то вот, вроде как, получилось
C++
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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include <iostream>
#include <ctime>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <graphics.h>
 
using namespace std;
 
int main()
{
    setlocale(0, "");
    srand(time(NULL));
    initwindow(1300, 700);
    
    int n = 0, u = 0, ax = 0, ay = 0, bx = 0, by = 0, cx = 0, cy = 0;
    float maxs = 0, p = 0, s = 0, ab = 0, ac = 0, bc = 0, a = 0, b = 0, c = 0, f = 0, v = 0, t = 0;
    
    cout << "Введите  n: ";
    cin >> n;
    
    if(n > 2)
    {
        int *x = new int[n];
        int *y = new int[n];
 
    
        for (int i = 0; i < n; i++)
        {
            x[i] = rand() % 1200;
            y[i] = rand() % 650;
            cout << "(" << x[i] << ", " << y[i] << ")" << endl;
            putpixel(x[i], y[i], 14);
        }
    
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                for (int k = 0; k < n; k++)
                {
                    if (j != i && k != j && k != i)
                    {
                        a = sqrt(pow((float)(x[i] - x[j]), 2) + pow((float)(y[i] - y[j]), 2));
                        b = sqrt(pow((float)(x[i] - x[k]), 2) + pow((float)(y[i] - y[k]), 2));
                        c = sqrt(pow((float)(x[k] - x[j]), 2) + pow((float)(y[k] - y[j]), 2));
                        p = (a + b + c) / 2;
                        s = sqrt(p * (p - a) * (p - b) * (p - c));
                        
                        if (s > maxs)
                        {
                            maxs = s;
                            ax = x[i];
                            ay = y[i];
                            bx = x[j];
                            by = y[j];
                            cx = x[k];
                            cy = y[k];
                        }
                    }
                }
            }
        }
        
        
        setcolor(3);
        line(ax, ay, bx, by);
        line(bx, by, cx, cy);
        line(ax, ay, cx, cy);
        
            
int x1 = ax, x2 = bx, x3 = cx, y1 = ay, y2 = by, y3 = cy; 
int x0, y0; 
 
 
for(int i = 0; i<n; i++) 
{ 
x0 = x[i]; 
y0 = y[i]; 
a = (x1 - x0) * (y2 - y1) - (x2 - x1) * (y1 - y0); 
b = (x2 - x0) * (y3 - y2) - (x3 - x2) * (y2 - y0); 
c = (x3 - x0) * (y1 - y3) - (x1 - x3) * (y3 - y0); 
 
if ((a >= 0 && b >= 0 && c >= 0) || (a <= 0 && b <= 0 && c <= 0)) 
{ 
putpixel(x[i], y[i], BLUE); 
} 
}
        
        cout << endl << "Максимальная площадь: " << maxs << endl << "Координаты вершин: "<< endl
            << "(" << ax << ", " << ay << ")" << endl
            << "(" << bx << ", " << by << ")" << endl
            << "(" << cx << ", " << cy << ")" << endl;
    }
    else
    {
        cout << "Ошибка ввода" << endl;
    }
    system("pause");
}
0
28.01.2016, 09:20
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
28.01.2016, 09:20
Помогаю со студенческими работами здесь

Найти наибольшую из площадей треугольников, вершины которых находятся в заданных точках
Извините, вверху неправильно написано. Должно быть так &quot;Найти наибольшую площадь&quot;. Ошибся ...

Найти наибольшую из площадей треугольников, вершины которых находятся в заданных точках
Здравствуйте! Написать программу на C++: Даны координаты 4-х точек x1,y1, x2,y2, x3,y3, x4,y4....

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

Найти наибольшую площадь треугольника
Даны значения двух вещественных массивов x и y размера n. Рассматривая пары значений (x1; y1),(x2;...


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

Или воспользуйтесь поиском по форуму:
15
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2023, CyberForum.ru