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

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

Восстановить пароль Регистрация
 
Arseny242
0 / 0 / 0
Регистрация: 29.09.2013
Сообщений: 27
30.03.2014, 09:10     Задача на структуры: выбор точек, образующих треугольник наибольшего периметра #1
Найти три различные точки из заданного множества точек, образующих треугольник наибольшего периметра.
Множество точек задано на плоскости.
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
30.03.2014, 09:10     Задача на структуры: выбор точек, образующих треугольник наибольшего периметра
Посмотрите здесь:

C++ Выбрать 3 разные точки заданного на плоскости множества точек,составляющие треугольник наибольшего периметра
C++ Квадрат наибольшего периметра
C++ Выбрать три разные точки заданного на плоскости множества точек, составляющие треугольник наибольшего периметра
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     Задача на структуры: выбор точек, образующих треугольник наибольшего периметра
Ответ Создать тему
Опции темы

Текущее время: 21:04. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru