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

Найти такую прямую, по разные стороны от которой лежат по N/2 точек - C++

Восстановить пароль Регистрация
 
dl07
1 / 1 / 0
Регистрация: 12.06.2010
Сообщений: 14
13.06.2010, 09:18     Найти такую прямую, по разные стороны от которой лежат по N/2 точек #1
Помогите написать программу:
Матрица N*2 задаёт координаты N точек плоскости (N-чётное число). Найти такую прямую, по разные стороны от которой лежат по N/2 точек
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.06.2010, 09:18     Найти такую прямую, по разные стороны от которой лежат по N/2 точек
Посмотрите здесь:

C++ Среди точек первого множества найти такую,которая принадлежит наибольшему количеству множеств.
Найти такую точку заданного на плоскости множества точек, сумма расстояний от которой до остальных минимальна C++
C++ Найти точку на плоскости, сумма расстояний от которой до остальных точек множества максимальна
C++ Найти точку, у которой сумма расстояний до других точек наименьшая
Найти такую точку, сумма расстояний от которой до остальных минимальна C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
dl07
1 / 1 / 0
Регистрация: 12.06.2010
Сообщений: 14
14.06.2010, 23:07  [ТС]     Найти такую прямую, по разные стороны от которой лежат по N/2 точек #2
Помогите написать программу или хотя бы подскажите алгоритм решеия.
besstiaa
 Аватар для besstiaa
93 / 93 / 7
Регистрация: 04.06.2010
Сообщений: 223
15.06.2010, 00:44     Найти такую прямую, по разные стороны от которой лежат по N/2 точек #3
Алгоритм решения... Это явно надо просто знать формулу(ы), и это уж явным образом не касается программирования. Зная теоретически, как это сделать, написать программку уже не трудно.
dl07
1 / 1 / 0
Регистрация: 12.06.2010
Сообщений: 14
15.06.2010, 22:50  [ТС]     Найти такую прямую, по разные стороны от которой лежат по N/2 точек #4
Пожалуста, помогите, кто нибудь...
dl07
1 / 1 / 0
Регистрация: 12.06.2010
Сообщений: 14
01.07.2010, 21:51  [ТС]     Найти такую прямую, по разные стороны от которой лежат по N/2 точек #5
Всё ещё актуально. Мучаюсь над этой прогой уже очень давно, даже не знаю с чего начать. Может у кого нить есть идеи как это сделать?
accept
4838 / 3237 / 165
Регистрация: 10.12.2008
Сообщений: 10,682
02.07.2010, 04:21     Найти такую прямую, по разные стороны от которой лежат по N/2 точек #6
найти все середины M((x1+x2)/2,(y1+y2)/2)
среди середин найти две такие, для которых N / 2 точек будут правее и N / 2 точек будут левее
по ходу перебором
Prividenie
74 / 74 / 6
Регистрация: 05.10.2008
Сообщений: 233
02.07.2010, 13:42     Найти такую прямую, по разные стороны от которой лежат по N/2 точек #7
Цитата Сообщение от dl07 Посмотреть сообщение
Матрица N*2

N - количество столбцов
2 - строк ?
accept
4838 / 3237 / 165
Регистрация: 10.12.2008
Сообщений: 10,682
02.07.2010, 13:49     Найти такую прямую, по разные стороны от которой лежат по N/2 точек #8
одна строка - одна точка
Mr.X
Эксперт С++
 Аватар для Mr.X
2807 / 1583 / 248
Регистрация: 03.05.2010
Сообщений: 3,688
03.07.2010, 20:37     Найти такую прямую, по разные стороны от которой лежат по N/2 точек #9
Сообщение было отмечено автором темы, экспертом или модератором как ответ
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
/////////////////////////////////////////////////////////////////////////////////
//Матрица N*2 задаёт координаты N точек плоскости (N-чётное число). 
//Найти такую прямую, по разные стороны от которой лежат по N/2 точек.
/////////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <cmath>
#include <complex>
#include <ctime>
#include <iomanip>
#include <iostream>
#include <set>
#include <vector>
 
typedef double                 T_coord;
typedef std::complex<T_coord>  T_point;
typedef std::vector<T_point>   T_points;
typedef std::vector<T_coord>   T_coords;
/////////////////////////////////////////////////////////////////////////////////
struct T_coord_compare
{
    bool operator() (T_coord  x1, T_coord  x2)
    {
        return x1 < x2
               && 0.0001 < x2 - x1;
    }
};
typedef std::set<T_coord, T_coord_compare>  T_coords_set;
/////////////////////////////////////////////////////////////////////////////////
struct T_point_compare
{
    bool operator() (T_point  z1, T_point  z2)
    {
        return z1.real() < z2.real()
               || z1.real() == z2.real()
                  && z1.imag() < z2.imag();
    }
};
typedef std::set<T_point, T_point_compare>  T_points_set;
/////////////////////////////////////////////////////////////////////////////////
void  get_coef_ABC_of_pryamaya
    (
        const T_points&  pryamaya,
        T_coord&         A,
        T_coord&         B,
        T_coord&         C
    )
{
    //Вычисляем коэффициенты ур-я прямой Ax + By + C = 0.
    T_point  z1 = pryamaya.front();
    T_point  z2 = pryamaya.back();
    if(z1.real() == z2.real())
    {
        A = 1;
        B = 0;
        C = -z1.real();
    }
    else
    {
        A = (z2.imag() - z1.imag()) / (z2.real() - z1.real());
        B = -1;
        C = z1.imag() - A * z1.real();
    }
}
/////////////////////////////////////////////////////////////////////////////////
T_points_set  get_points_po_odnu_stor_ot_nach_coord
    (
        bool                 po_odnu_stor_ot_nach_coord, 
        const T_points&      pryamaya, 
        const T_points_set&  points_set
    )
{
    T_coord  A;
    T_coord  B;
    T_coord  C;
    get_coef_ABC_of_pryamaya(pryamaya, A, B, C);
 
    struct T_is_po_odnu_stor_ot_nach_coord
    {
        bool  is_po_odnu_stor_ot_nach_coord_;
        T_coord  A_;
        T_coord  B_;
        T_coord  C_;
 
        T_is_po_odnu_stor_ot_nach_coord
            (
                bool     is_po_odnu_stor_ot_nach_coord,
                T_coord  A,
                T_coord  B,
                T_coord  C
            )
            : is_po_odnu_stor_ot_nach_coord_(is_po_odnu_stor_ot_nach_coord),
              A_(A), B_(B), C_(C)
        {
            if(C_ > 0)
            {
                A_ *= -1;
                B_ *= -1;
                C_ *= -1;
            }        
        }
        bool operator() (const T_point&  point) const
        {
            return A_ * point.real() + B_ * point.imag() + C_ < 0
            == is_po_odnu_stor_ot_nach_coord_;
        }
    };
    T_points_set  res_points_set;
    std::remove_copy_if(points_set.begin(), points_set.end(),
                        std::inserter(res_points_set, res_points_set.begin()),
                        T_is_po_odnu_stor_ot_nach_coord
                            (!po_odnu_stor_ot_nach_coord, A, B, C));
    return  res_points_set;
}
/////////////////////////////////////////////////////////////////////////////////
void  print_pryamaya(const T_points&  pryamaya)
{
    //Печатаем ур-ние прямой с угловым коэффициентом.
    T_coord  A;
    T_coord  B;
    T_coord  C;
    get_coef_ABC_of_pryamaya(pryamaya, A, B, C);
    //Получили коэффициенты прямой вида Ax +By + C = 0.
    if(B == 0)
    {
        //Печатаем ур-ние вида X = x1.
        std::cout << "x = "
                  << -C
                  << std::endl;    
    }
    else
    {
        //Печатаем ур-ние вида Y = kX + b.
        std::cout << "Y = ";
        if(A)
        {
            T_coord  k = -A / B;
            std::cout << k
                      << "X "; 
        }
        if(C)
        {
            T_coord  b = -C / B;
            std::cout << (b > 0 ? "+ " : "- ")
                      << abs(b);       
        }
        std::cout << std::endl;    
    }
}
/////////////////////////////////////////////////////////////////////////////////
void  print_points(const T_points_set&  points_set)
{    
    struct  T_print_point
    {
        int cur_num_;
        T_print_point() : cur_num_(1)
        {}
        void  operator() (const T_point&  point)
        {
            std::cout << std::setw(2)
                      << cur_num_++
                      << ": "
                      << point
                      << std::endl;
        }
    };    
    std::for_each(points_set.begin(), points_set.end(), T_print_point());
}
/////////////////////////////////////////////////////////////////////////////////
T_points_set  get_rand_points(size_t  points_total)
{
    const int MIN_XY_COORD = 0;
    const int MAX_XY_COORD = 10;
    T_points_set  rand_points_set;
    do
    {
        int  rand_X = rand() % MAX_XY_COORD + MIN_XY_COORD;
        int  rand_Y = rand() % MAX_XY_COORD + MIN_XY_COORD;
        rand_points_set.insert(T_point(rand_X, rand_Y));
    }while(rand_points_set.size() < points_total);
    return  rand_points_set;
}
/////////////////////////////////////////////////////////////////////////////////
T_points  get_pryamaya_delit_popolam(const T_points_set&  points_set)
{
    struct T_get_X_coord
    {
        T_coord operator() (T_point z)
        {
            return z.real();
        }
    };
    //Поворачиваем все заданные точки против часовой стрелки, пока 
    //проекции заданных точек на ось X не станут все различными.
    T_coords_set  X_coords_set;
    T_point       mnojitel = 1;    
    for(T_coord  coef = 2; ; ++coef)
    { 
        T_points_set  points_set_povernutye;
        std::transform(points_set.begin(), points_set.end(),                       
                       std::inserter(points_set_povernutye, points_set_povernutye.begin()),
                       std::bind2nd(std::multiplies<T_point>(), mnojitel));
 
        X_coords_set.clear();
        std::transform(points_set_povernutye.begin(), points_set_povernutye.end(),                       
                       std::inserter(X_coords_set, X_coords_set.begin()),
                       T_get_X_coord());
 
        if(X_coords_set.size() == points_set.size()) break;
        T_coord  ugol_v_rad = atan(1 / coef);
        mnojitel = std::polar(1.0, ugol_v_rad);        
    }
    //Проводим вертикальную прямую, деля пополам множество координат X.
    T_coords  X_coords(X_coords_set.begin(), X_coords_set.end());
    int       m = points_set.size();
    T_coord   x1 = X_coords[m / 2 - 1];
    T_coord   x2 = X_coords[m / 2];
    T_coord   x_pryam = (x1 + x2) / 2.0;
    T_point   z1_pryam(x_pryam);
    T_point   z2_pryam(x_pryam, 1);
    T_points  pryamaya; 
    pryamaya.push_back(z1_pryam);
    pryamaya.push_back(z2_pryam);
    //Поворачиваем точки прямой обратно по часовой стрелке.
    std::transform(pryamaya.begin(), pryamaya.end(),
                   pryamaya.begin(),
                   std::bind2nd(std::multiplies<T_point>(), 1.0 / mnojitel));
    return  pryamaya;
}
/////////////////////////////////////////////////////////////////////////////////
int main()
{
    std::locale::global(std::locale(""));
    srand(static_cast<unsigned>(time(0)));
 
    const int MIN_N = 1;
    const int MAX_N = 10;
 
    int  rand_n = rand() % MAX_N + MIN_N;
    int  points_total = rand_n * 2;
    std::cout << "Выбираем случайные точки в количестве "
              << points_total
              << ":"
              << std::endl;
    
    T_points_set  points_set = get_rand_points(points_total);
    print_points(points_set);
    std::cout << "Программа проводит прямую: "
              << std::endl;
    
    T_points  pryamaya = get_pryamaya_delit_popolam(points_set);
    print_pryamaya(pryamaya);
 
    std::cout << "Относительно этой прямой точки расположены так:"
              << std::endl
              << "по одну сторону с началом координат:"
              << std::endl;
    print_points(get_points_po_odnu_stor_ot_nach_coord(true, pryamaya, points_set));
    std::cout << "по другую сторону от начала координат:"
              << std::endl;
    print_points(get_points_po_odnu_stor_ot_nach_coord(false, pryamaya, points_set));
    return 0;
}
dl07
1 / 1 / 0
Регистрация: 12.06.2010
Сообщений: 14
05.07.2010, 14:29  [ТС]     Найти такую прямую, по разные стороны от которой лежат по N/2 точек #10
Спасибо, буду разбираться, чесно говоря мало что тут понял, но программа впечатляет.
Вы не могли бы кратко пояснить по какому принципу происходит выбор прямой?
Mr.X
Эксперт С++
 Аватар для Mr.X
2807 / 1583 / 248
Регистрация: 03.05.2010
Сообщений: 3,688
05.07.2010, 18:31     Найти такую прямую, по разные стороны от которой лежат по N/2 точек #11
Цитата Сообщение от dl07 Посмотреть сообщение
Вы не могли бы кратко пояснить по какому принципу происходит выбор прямой?
Я ж там в комментариях написал. В цикле поворачиваем все заданные точки вокруг начала координат, пока их проекции на ось Х не станут все различными. Затем задаем вертикальную прямую, делящую проекции точек на ось Х пополам, двумя точками. Затем поворачиваем эти точки прямой на тот же угол обратно.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.07.2010, 21:29     Найти такую прямую, по разные стороны от которой лежат по N/2 точек
Еще ссылки по теме:

C++ Массив: Найти такую неразрывную последовательность положительных чисел, сумма элементов у которой максимальная.
C++ Найти такую точку, что шар радиуса R с центром в этой точке содержит максимальное число точек зад
Задать массив точек, и определить радиус и центр окружности, на которой лежит наибольшее число точек C++

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

Или воспользуйтесь поиском по форуму:
dl07
1 / 1 / 0
Регистрация: 12.06.2010
Сообщений: 14
05.07.2010, 21:29  [ТС]     Найти такую прямую, по разные стороны от которой лежат по N/2 точек #12
Спасибо, теперь понятно для чего поворачивали точки, больше вопросов нет
Yandex
Объявления
05.07.2010, 21:29     Найти такую прямую, по разные стороны от которой лежат по N/2 точек
Ответ Создать тему
Опции темы

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