Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Arseny242
0 / 0 / 0
Регистрация: 29.09.2013
Сообщений: 27
#1

Задача на структуры: выбор точек, образующих треугольник наибольшего периметра - C++

30.03.2014, 09:10. Просмотров 745. Ответов 4
Метки нет (Все метки)

Найти три различные точки из заданного множества точек, образующих треугольник наибольшего периметра.
Множество точек задано на плоскости.
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
30.03.2014, 09:10     Задача на структуры: выбор точек, образующих треугольник наибольшего периметра
Посмотрите здесь:
C++ Выбрать 3 разные точки заданного на плоскости множества точек,составляющие треугольник наибольшего периметра
C++ Из заданного на плоскости множества точек выбрать такие три, которые составляют треугольник наибольшего периметра.
C++ Выбрать три разные точки заданного на плоскости множества точек, составляющие треугольник наибольшего периметра
Треугольник наибольшего периметра C++
Выбрать 3 точки множества, составляющих треугольник наибольшего периметра C++
Квадрат наибольшего периметра C++
C++ Квадрат наибольшего периметра
C++ Найти квадрат наибольшего периметра
Выбрать из точек множества три таких, чтобы в получившийся треугольник влезо наибольшее количество точек C++
Организовать класс треугольник определенный по 3-ем сторонам содержащий методы нахождения периметра и площади(По формуле герона) C++
Создать производные классы: Rectangle (прямоугольник), Circle (круг), Triangle (треугольник) со своими методами вычисления площади и периметра C++
Задача на вычисление площади и периметра C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Winorun
38 / 38 / 4
Регистрация: 03.05.2013
Сообщений: 177
30.03.2014, 09:40     Задача на структуры: выбор точек, образующих треугольник наибольшего периметра #2
производишь выборку трех точек из множества считаешь периметр запоминаешь мах . В чем проблема укажи конкретней
IrineK
Заблокирован
30.03.2014, 09:43     Задача на структуры: выбор точек, образующих треугольник наибольшего периметра #3
Цитата Сообщение от Winorun Посмотреть сообщение
производишь выборку трех точек из множества считаешь периметр запоминаешь мах
производишь выборку трех точек из множества
производишь проверку на существование треугольника
считаешь периметр
запоминаешь мах
IrineK
Заблокирован
30.03.2014, 12:44     Задача на структуры: выбор точек, образующих треугольник наибольшего периметра #4
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Ну вот, даже с картинкой )

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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
#include <iostream>
#include <ctime>
#include <cmath>
#include <Windows.h>
 
POINT **CreateArray (int N)
{   int i;
    POINT **arr = new POINT*[N];
    for (i = 0; i<N; i++)
    {   arr[i] = new POINT;
        arr[i]->x = rand()%300 + 100;
        arr[i]->y = rand()%100 + 100;
    }
    return arr;
}
 
void DeleteArray (POINT** arr, int N)
{   for (int i = 0; i<N; i++)
        delete arr[i];
    delete [] arr;
}
 
void ShowArray (HDC hDC, POINT** arr, int N, COLORREF color)
{   printf("points:\n");
    for (int i = 0; i<N; i++)
    {   SetPixel(hDC, arr[i]->x, arr[i]->y, color);
        SetPixel(hDC, arr[i]->x-1, arr[i]->y-1, color);
        SetPixel(hDC, arr[i]->x+1, arr[i]->y+1, color);
        SetPixel(hDC, arr[i]->x-1, arr[i]->y+1, color);
        SetPixel(hDC, arr[i]->x+1, arr[i]->y-1, color);
        printf("(%d, %d)\n", arr[i]->x, arr[i]->y);
    }   
}
 
typedef struct _TTriangle
{   POINT *A, *B, *C;
    double a,b,c;
    double perimeter;
}   TTriangle;
 
int IsTriangle (POINT *A, POINT * B, POINT *C)
{   return (B->x - A->x) * (C->y - A->y) - (C->x - A->x) * (B->y - A->y);
}
 
double Length (POINT *A, POINT * B)
{   return sqrt (1.*(A->x - B->x) * (A->x - B->x) + (A->y - B->y)*(A->y - B->y));
}
 
TTriangle **CreateTriangles (POINT** arr, int N, int M)
{   int count = 0, i, j, k;
    TTriangle **tri = new TTriangle*[M];
    for (i = 0; i<M; i++)
    {   tri[i] = new TTriangle;
        tri[i]->A = new POINT;
        tri[i]->B = new POINT;
        tri[i]->C = new POINT;
    }
 
    for (i = 0; i<N-2; i++)
        for (j = i+1; j<N-1; j++)
            for (k = j+1; k<N; k++)
            {   tri[count]->A->x = arr[i]->x; tri[count]->A->y = arr[i]->y;
                tri[count]->B->x = arr[j]->x; tri[count]->B->y = arr[j]->y;
                tri[count]->C->x = arr[k]->x; tri[count]->C->y = arr[k]->y;
 
                if(!IsTriangle (tri[count]->A, tri[count]->B, tri[count]->C))
                    tri[count]->a = tri[count]->b = tri[count]->c = 0.;
                else
                {   tri[count]->a = Length (tri[count]->B,  tri[count]->C);
                    tri[count]->b = Length (tri[count]->A,  tri[count]->C);
                    tri[count]->c = Length (tri[count]->A,  tri[count]->B);
                }
                tri[count]->perimeter = tri[count]->a + tri[count]->b + tri[count]->c;
                count++;
            }
 
    return tri;
}
 
void DeleteTri (TTriangle *t)
{   delete t->A;
    delete t->B;
    delete t->C;
    delete t;
}
 
void DeleteTriangles (TTriangle **tri, int M)
{   for (int i = 0; i<M; i++)
        DeleteTri (tri[i]);
    delete [] tri;
}
 
TTriangle *GetTriMaxPerimeter (TTriangle **tri, int M)
{   int pos = 0, i = 0;
    double max = 0.;
    for ( ; i<M; i++)
        if (tri[i]->perimeter > max)
        {   max = tri[i]->perimeter;
            pos = i;
        }
    TTriangle *found = new TTriangle;
    found->A = new POINT;
    found->B = new POINT;
    found->C = new POINT;
 
    found->A->x = tri[pos]->A->x; found->A->y = tri[pos]->A->y;
    found->B->x = tri[pos]->B->x; found->B->y = tri[pos]->B->y;
    found->C->x = tri[pos]->C->x; found->C->y = tri[pos]->C->y;
    found->a = tri[pos]->a;
    found->b = tri[pos]->b;
    found->c = tri[pos]->c;
    found->perimeter = tri[pos]->perimeter;
 
    return found;
}
 
void ShowTriangle (HDC hDC, TTriangle *t)
{   HPEN hPen = CreatePen(PS_SOLID, 3, RGB(255,0,0));
    SelectObject(hDC, hPen);
    POINT p;
    
    GetCurrentPositionEx(hDC, &p);
    MoveToEx(hDC, t->A->x, t->A->y, &p);
    LineTo (hDC, t->B->x, t->B->y);
    LineTo (hDC, t->C->x, t->C->y);
    LineTo (hDC, t->A->x, t->A->y);
 
    printf("\n\n\n\n\n\n\nmax perimeter: %.3lf\n", t->perimeter);
    printf("triangle:\n(%d, %d)\n(%d, %d)\n(%d, %d)\n", t->A->x, t->A->y, t->B->x, t->B->y, t->C->x, t->C->y);
    
    DeleteObject (hPen);
}
 
 
 
int main()
{   int N = 10;
    HDC hDC = GetDC(GetConsoleWindow());
    srand ((unsigned int) time (NULL));
    
    POINT **points = CreateArray (N);
    ShowArray (hDC, points, N, RGB (255,255,0));
 
    int M = N*(N-1)*(N-2) / 6;
    TTriangle **tri = CreateTriangles (points, N, M);
 
    TTriangle *found = GetTriMaxPerimeter (tri, M);
    ShowTriangle (hDC, found);
 
    DeleteArray (points, N);
    DeleteTriangles (tri, M);
    DeleteTri (found);
 
    getchar();
    return 0;
}
Миниатюры
Задача на структуры: выбор точек, образующих треугольник наибольшего периметра  
Arseny242
0 / 0 / 0
Регистрация: 29.09.2013
Сообщений: 27
30.03.2014, 21:44  [ТС]     Задача на структуры: выбор точек, образующих треугольник наибольшего периметра #5
У меня есть программа, которая находит точку, сумма расстояний от которой до остальных точек множества минимальна.
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
#include <cmath>
#include <iostream>
#include<fstream>
using namespace std;
struct point
{
double x,y;
};
double length(double a, double b, double a1, double b1)
{
return sqrt(pow(a-a1,2)+pow(b-b1,2));
}
int main()
{ ifstream in("input.txt");
ofstream out("output.txt");
int n;point p[100];
    while (in.peek()!=EOF)
{in >> n;
for (int i=0; i<n; i++)
in >> p[i].x >> p[i].y;
double s[100];
for (int i=0; i<n; i++)
{
double sum=0;
for (int j=0; j<n; j++)
{sum += length(p[i].x,p[i].y, p[j].x, p[j].y);
}
s[i] = sum;
}
double min=s[0]; int nmin=0;
for (int i=0; i<n; i++)
if (min > s[i]) {min = s[i]; nmin=i;}
cout<<"Minimalnoe rasstoyanie="<<min<<endl<<"Tochka ("<<p[nmin].x<<", "<<p[nmin].y<<")"<<endl;
}
in.close();
out.close();
return 0;
}
Как ее переделать для поиска трех точек, мне пока непонятно.
Yandex
Объявления
30.03.2014, 21:44     Задача на структуры: выбор точек, образующих треугольник наибольшего периметра
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru