Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

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

Из множества точек на плоскости найти точки, образующие параллелограмм с наибольшим количеством точек внутри - C++

22.12.2016, 02:04. Просмотров 371. Ответов 4
Метки нет (Все метки)

"Даны N точек на плоскости. Найти среди них точки являющиеся вершинами фигуры, содержащей максимальное число заданных точек. Фигура - параллелограм."
Можете объяснить всю математику задачи пожалуйста.
0
Лучшие ответы (1)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
22.12.2016, 02:04
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Из множества точек на плоскости найти точки, образующие параллелограмм с наибольшим количеством точек внутри (C++):

Найти паралелограмм с наибольшим количеством точек - C++
Приветствую всех. Обращаюсь с помощью, так как эта программа уже выводит меня из себя. Задание состоит в следующем: "Даны N точек на...

Из заданного на плоскости множества точек выбрать три различные точки - C++
Само задание звучит так: "Из заданного на плоскости множества точек выбрать три различные точки так, чтобы разность между площадью...

Из заданного на плоскости множества точек выбрать три различные точки - C++
Здравствуйте, помогите пожалуйста написать программу: Из заданного на плоскости множества точек выбрать три различные точки так, чтобы...

Из заданного множества точек на плоскости выбрать три разные точки A, B, C - C++
Из заданного множества точек на плоскости выбрать три разные точки A, B, C, так, чтобы внутри треугольника ABC содержалось максимальное...

Из заданного множества точек на плоскости выбрать две различные точки - C++
Из заданного множества точек на плоскости выбрать две различные точки так, что бы количества точек, лежащих по разные стороны прямой,...

Из задоного множества точек на плоскости выбрать две различные точки - C++
Привет всем пожалуста помогите найти ошибку в коде. условия задачи: Из задоного множества точек на плоскости выбрать две различные точки...

4
afront
1047 / 993 / 374
Регистрация: 29.02.2016
Сообщений: 3,185
22.12.2016, 09:54 #2
http://math.stackexchange.com/questi...de-a-rectangle
0
abaranci
0 / 0 / 0
Регистрация: 09.01.2015
Сообщений: 73
22.12.2016, 14:47  [ТС] #3
Я не могу найти все параллелограммы. А так остальное работает правильно вроде
0
afront
1047 / 993 / 374
Регистрация: 29.02.2016
Сообщений: 3,185
22.12.2016, 15:02 #4
http://stackoverflow.com/questions/7...gles-algorithm
0
Mr.X
Эксперт С++
3060 / 1705 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
23.12.2016, 10:09 #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
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
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
///////////////////////////////////////////////////////////////////////////////
//2.
///////////////////////////////////////////////////////////////////////////////
//Даны N точек на плоскости. Найти среди них точки
//являющиеся вершинами фигуры, содержащей максимальное
//число заданных точек. Фигура - параллелограмм.
///////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <complex>
#include <iostream>
#include <iterator>
#include <numeric>
#include <set>
#include <utility>
#include <vector>
///////////////////////////////////////////////////////////////////////////////
typedef double                          T_coord;
typedef std::complex    < T_coord   >   T_point;
typedef std::vector     < T_point   >   T_points_arr;
///////////////////////////////////////////////////////////////////////////////
namespace std
{
    bool    operator<
        (
            T_point     const   &   L,
            T_point     const   &   R
        )
    {
        return      std::make_pair(     L.real(),   L.imag()    )
                <   std::make_pair(     R.real(),   R.imag()    );
    }
}
///////////////////////////////////////////////////////////////////////////////
typedef std::set    < T_point   >   T_points;
typedef std::set    < T_points  >   T_parallelograms;
///////////////////////////////////////////////////////////////////////////////
T_coord     pseudoscalar
    (
        T_point     const   &   L,
        T_point     const   &   R
    )
{
    return      L.real  ()  *   R.imag  ()
            -   L.imag  ()  *   R.real  ();
}
///////////////////////////////////////////////////////////////////////////////
bool    triad_is_collinear( T_points_arr    const   &   triad )
{
    auto    A   =   triad[0];
    auto    B   =   triad[1];
    auto    C   =   triad[2];
 
    return      pseudoscalar
                    (
                        B   -   A,
                        C   -   A
                    )
 
            ==  0;
}
///////////////////////////////////////////////////////////////////////////////
void    add_parallelograms_of_triad
    (
        T_points            const   &   points,
        T_points_arr                    triad,
        T_parallelograms            &   parallelograms
    )
{
    if  (
            triad_is_collinear( triad )
        )
    {
        return;
    }
 
    for( size_t  i{}; i < triad.size(); ++i )
    {
        auto    A   =   triad[0];
        auto    B   =   triad[1];
        auto    C   =   triad[2];
 
        auto    D   =   -A + B + C;
 
        if  (
                points.count( D )
            )
        {
            parallelograms.insert   (
                                        {A, B, C, D}
                                    );
        }
 
        std::rotate
            (
                triad.begin     (),
                triad.begin     ()  +   1,
                triad.end       ()
            );
    }//for
}
///////////////////////////////////////////////////////////////////////////////
void    set_parallelograms_for_points
    (
        T_points    const   &   points,
        T_parallelograms    &   parallelograms
    )
{
    for (
            auto
            it_1  =   points.begin    ();
            it_1  !=  points.end      ();
            ++it_1
        )
    {
        for (
                auto
                it_2    =   std::next   ( it_1 );
                it_2    !=  points.end  ();
                ++it_2
            )
        {
            for (
                    auto
                    it_3    =   std::next   ( it_2 );
                    it_3    !=  points.end  ();
                    ++it_3
                )
            {
                add_parallelograms_of_triad
                    (
                        points,
                        {   *it_1,  *it_2,  *it_3   },
                        parallelograms
                    );
            }//for
        }//for
    }//for
}
///////////////////////////////////////////////////////////////////////////////
struct  T_point_is_inside_of_par
{
    //-------------------------------------------------------------------------
    T_points_arr    par_arr_;
    T_point         center_;
    //-------------------------------------------------------------------------
    T_point_is_inside_of_par( T_points     const   &   par )
        :
        par_arr_    (
                        par.begin   (),
                        par.end     ()
                    )
    {
        center_     =       std::accumulate
                                (
                                    par_arr_.begin  (),
                                    par_arr_.end    (),
                                    T_point         ()
                                )
 
                        /   T_point(    par_arr_.size()  );
 
        std::sort
            (
                par_arr_.begin   (),
                par_arr_.end     (),
 
                [&]             (
                                    auto  const   &   L,
                                    auto  const   &   R
                                )
                {
                    return      std::arg( L     -   center_ )
                            <   std::arg( R     -   center_ );
                }
            );
    }
    //-------------------------------------------------------------------------
    bool    operator()  ( T_point   const   &   p )
    {
        bool    bool_res{};
 
        for( size_t  i{}; i < par_arr_.size(); ++i )
        {
            bool_res    =   points_lie_on_one_side_of_segment
                                (
                                    p,
                                    center_,
 
                                    par_arr_[0],
                                    par_arr_[1]
                                );
 
            if( !bool_res )
            {
                break;
            }
 
            std::rotate
                (
                    par_arr_.begin  (),
                    par_arr_.begin  ()  +   1,
                    par_arr_.end    ()
                );
        }//for
 
        return  bool_res;
    }
    //-------------------------------------------------------------------------
    static
    bool    points_lie_on_one_side_of_segment
        (
            T_point     const   &   L,
            T_point     const   &   R,
 
            T_point     const   &   segm_v_1,
            T_point     const   &   segm_v_2
        )
    {
        return          pseudoscalar
                            (
                                L           -   segm_v_1,
                                segm_v_2    -   segm_v_1
                            )
 
                    *   pseudoscalar
                            (
                                R           -   segm_v_1,
                                segm_v_2    -   segm_v_1
                            )
 
                >=  0;
    }
    //-------------------------------------------------------------------------
};
///////////////////////////////////////////////////////////////////////////////
struct  T_points_count_of_par
{
    //-------------------------------------------------------------------------
    T_points    const   &   points_;
    //-------------------------------------------------------------------------
    T_points_count_of_par( T_points     const   &   points  )
        :
        points_( points )
    {}
    //-------------------------------------------------------------------------
    int     operator()  ( T_points  const   &   par )                       const
    {
        return  std::count_if
                    (
                        points_.begin               (),
                        points_.end                 (),
                        T_point_is_inside_of_par    ( par )
                    );
    }
    //-------------------------------------------------------------------------
};
///////////////////////////////////////////////////////////////////////////////
void    set_parallelogram_containing_max_number_of_points
    (
        T_points    const   &   points,
        T_points            &   res_parallelogram
    )
{
    T_parallelograms    parallelograms;
 
    set_parallelograms_for_points
        (
            points,
            parallelograms
        );
 
    T_points_count_of_par  points_count_of_par( points );
 
    auto    it  =   std::max_element
                        (
                            parallelograms.begin    (),
                            parallelograms.end      (),
 
                            [&]                     (
                                                        auto  const   &   L,
                                                        auto  const   &   R
                                                    )
                            {
                                return      points_count_of_par(L)
                                        <   points_count_of_par(R);
                            }
                        );
 
    if  (
                it
            !=  parallelograms.end()
        )
    {
        res_parallelogram   =   *it;
    }
}
///////////////////////////////////////////////////////////////////////////////
int     main()
{
    size_t  n{};
    std::cout   <<  "points total: ";
    std::cin    >>  n;
 
    std::cout   <<  "Input "
                <<  n
                <<  " points in form (1,2):"
                <<  std::endl;
 
    T_points    points;
 
    while   (
                    points.size()
                <   n
            )
    {
        T_point     point_cur;
 
        do
        {
            std::cout   <<  "point_"
                        <<  points.size() + 1
                        <<  "\t: ";
 
            std::cin    >>  point_cur;
        }
        while   (
                        !points.empty   ()
                    &&  points.count    ( point_cur )
                );
 
        points.emplace( point_cur );
    }//while
 
    T_points    res_parallelogram;
 
    set_parallelogram_containing_max_number_of_points
        (
            points,
            res_parallelogram
        );
 
    if  (
            res_parallelogram.empty()
        )
    {
        std::cout   <<  "no solution"
                    <<  std::endl;
    }
    else
    {
        std::cout   <<  "resulting parallelogram:"
                    <<  std::endl;
        for( auto   const   &   point   :   res_parallelogram )
        {
            std::cout   <<  point
                        <<  '\t';
        }//for
 
        std::cout   <<  std::endl;
    }//else
}
1
23.12.2016, 10:09
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
23.12.2016, 10:09
Привет! Вот еще темы с ответами:

Из заданного множества точек на плоскости выбрать две различные точки так - C++
Из заданного множества точек на плоскости выбрать две различные точки так, чтобы количество точек, лежащих по разные стороны от прямой,...

Выбрать 3 разные точки заданного на плоскости множества точек,составляющие треугольник наибольшего периметра - C++
Подкиньте идею...

Работа С Массивами (Выбрать три различные точки из заданного множества точек на плоскости так...) - C++
Задание: Выбрать три различные точки из заданного множества точек на плоскости так, чтобы была минимальной разность между количествами...

Выбрать три разные точки заданного на плоскости множества точек, составляющие треугольник наибольшего периметра - C++
Задание, как множество точек вывести на экран понял. #include &lt;iostream&gt; #include &lt;time.h&gt; #define _CRT_SECURE_NO_DEPRECATE 0 using...


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

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

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