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

Расстояние - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Функции http://www.cyberforum.ru/cpp-beginners/thread211405.html
Написать програму по C/C++ по теме:вычеслить и запомнить количество отрицательных елементов каждого столбца для матриц А(10;10) В(15;20) Вот пример от другой програмы:Вычеслить суммы положительных элементов массивов Х(N),Y(M),Z(K) N<=60,M<=60,K<=70. Вот решение: #include<conio.h> #include<stdlib.h> #include<iostream.h> #include<stdio.h> int sum(int *a, int n)
C++ НОК массива "Си" Помогите найти НОК всех целых чисел одномерного массива.... http://www.cyberforum.ru/cpp-beginners/thread211394.html
Вычисление функции результат в файл C++
Помогите написать программу которая будит обсчитывать функцию, например (sin(x)+x-1) и записывает результат в файл. шаг и отрезок задавать с клавиатуры Использовать библиотеку math.h
Комментарии к сортировке методом Шелла C++
#include <conio.h> #include <stdio.h> void shellSort(int a, int n); void mini_sort(int A,int m,int i); void main() { int z,A={56,345,57,34,678,567,43,12,65,47,689,38,24,67}; for (z=0;z<14;z++) printf ("%d ",A); printf("\n\n");
C++ Шелл, Хоар, слияние + шаблоны http://www.cyberforum.ru/cpp-beginners/thread211386.html
Кто может посодействовать в ниписании такой проги? шелл хоар и слияние... так чтобы было в начале меню с выбором каким методом сортировать? и чтобы там можно было делать сортировку массивов? ОЧЕНЬ ПРОШУ, НУЖНА ПОМОШЬ!!!
C++ Класс Квадрат: ввод, перемещение на плоскости Нужно создать квадрат с помощью классов, один из методов перемещение на плоскости. Помогите, пож., как ввести квадрат, не используя графику. Заранее спасибо! подробнее

Показать сообщение отдельно
Mr.X
Эксперт С++
3048 / 1693 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
20.12.2010, 18:23     Расстояние
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
/////////////////////////////////////////////////////////////////////////////////////
//На плоскости своими координатами задано N точек. Рассмотрим набор прямых, 
//проведенных через все различные пары точек. Необходимо определить 
//наибольшее возможное расстояние от любой заданной точки, до любой 
//прямой построенной по двум другим точкам.
/////////////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <cmath>
#include <complex>
#include <cstdlib>
#include <iostream>
#include <limits>
#include <set>
#include <vector>
/////////////////////////////////////////////////////////////////////////////////////
typedef double                 T_coord;
typedef std::complex<T_coord>  T_point;
typedef std::vector<T_point>   T_points;
/////////////////////////////////////////////////////////////////////////////////////
template<class T>
bool  equal_to_for_real(T a, T b) 
{
    const T  coef = 10;
    return abs(a - b) < std::numeric_limits<T>::epsilon() * coef;
}
/////////////////////////////////////////////////////////////////////////////////////
template<class T>
bool  greater_for_real(T a, T b) 
{
    return a > b
           && !equal_to_for_real(a, b);
}
/////////////////////////////////////////////////////////////////////////////////////
template<class T>
bool  less_for_real(T a, T b) 
{
    return a < b
           && !equal_to_for_real(a, b);
}
/////////////////////////////////////////////////////////////////////////////////////
template<class T>
bool  greater_equal_for_real(T a, T b) 
{
    return !less_for_real(a, b);
}
/////////////////////////////////////////////////////////////////////////////////////
template<class T>
bool  less_equal_for_real(T a, T b) 
{
    return !greater_for_real(a, b);
}
/////////////////////////////////////////////////////////////////////////////////////
struct  T_bottom_left_compare
{
    bool operator() (T_point A, T_point B)
    {
        return equal_to_for_real(A.imag(), B.imag()) 
            ? less_for_real(A.real(), B.real()) : less_for_real(A.imag(), B.imag());
    }
};
/////////////////////////////////////////////////////////////////////////////////////
struct  T_polar_corner_compare
{   
    bool  operator() (T_point A, T_point B)
    {
        return equal_to_for_real(arg(A), arg(B)) 
                   ? less_for_real(abs(A), abs(B)) 
                   : less_for_real(arg(A), arg(B));
    }
};
/////////////////////////////////////////////////////////////////////////////////////
T_point  vect(T_point  A, T_point  B)
{
    return B - A;
}
/////////////////////////////////////////////////////////////////////////////////////
T_coord  det(T_point A, T_point B)
{
    return  A.real() * B.imag() - A.imag() * B.real();
}
/////////////////////////////////////////////////////////////////////////////////////
T_points  get_convex_hull_points(const T_points&  points)
{
    //Ищем выпуклую оболочку методом Грэхема (время работы O(n*lg(n))).
    
    //Находим левую из самых нижних точек заданной совокупности.
    T_point  bottom_point_old 
        = *std::min_element(points.begin(), points.end(), T_bottom_left_compare());    
    
    //Вычитаем из всех точек вектора точку bottom_point_old (тогда стартовая точка
    //переместится в начало координат) и записываем эти точки в множество, 
    //отсортированное по полярному углу.
    typedef std::set<T_point, T_polar_corner_compare>  T_convex_hull_points;
    T_convex_hull_points  convex_hull_points;
    
    std::transform(points.begin(), points.end(), 
                   std::inserter(convex_hull_points, convex_hull_points.begin()), 
                   std::bind2nd(std::minus<T_point>(), bottom_point_old));
 
    T_point  bottom_point = T_point();
 
    //Помещаем в стек стартовую точку и первую точку множества, удаляя их из множества.    
    T_points  stack;
 
    T_point  cur_point = bottom_point;
    stack.push_back           (cur_point);
    convex_hull_points.erase  (cur_point);
 
    cur_point = *convex_hull_points.begin();
    stack.push_back           (cur_point);
    convex_hull_points.erase  (cur_point);
 
    //В цикле проверяем, какой поворот образуют точки предпоследняя в стеке,
    //последняя в стеке, и текущая. Если это не левый поворот, то выталкиваем
    //точку из стека (если она там не одна), и вставляем туда текущую. 
    //В конце в стеке останутся точки оболочки.
    for(T_convex_hull_points::const_iterator  point_it = convex_hull_points.begin();
        point_it != convex_hull_points.end(); )
    {
        int last_ind       = stack.size()  - 1;
        int prev_last_ind  = last_ind      - 1;
        T_point  v1 = vect(stack[prev_last_ind], stack[last_ind]);    
        T_point  v2 = vect(stack[last_ind], *point_it); 
 
        if(det(v1, v2) <= 0)
        {
            stack.pop_back();
            if(1 < stack.size())
            {
                continue;
            }            
        }
        stack.push_back(*point_it);
        ++point_it;
    }
    //Прибавляем к каждой точке stack точку bottom_point_old.
    std::transform(stack.begin(), stack.end(), stack.begin(),                   
                   std::bind2nd(std::plus<T_point>(), bottom_point_old));
 
    return  stack;  
}
/////////////////////////////////////////////////////////////////////////////////////
T_coord  get_max_dist_from_point_to_line
    (
        T_points&  points,
        T_point&   A,
        T_point&   B,
        T_point&   C
    )
{
    const T_points  convex_hull_points  = get_convex_hull_points(points);
    T_coord         H_max               = 0;
    //Очевидно, что если в заданном множестве точка A и прямая BC являются искомыми, 
    //то точка A принадлежит выпуклой оболочке множества, т.е. достаточно сравнивать 
    //расстояния от прямых, проходящих через пары точек множества, до точек выпуклой оболочки.
    //
    //Очевидно также, что среди пар точек множества может встретиться много таких, 
    //что прямые, проходящие через них, расположены к точкам выпуклой оболочки гораздо ближе,
    //чем прямые, проходящие через пары точек выпуклой оболочки, поэтому логично
    //точки выпуклой оболочки поставить в начало вектора.
    struct  T_is_convex_hull_point
    {
        const T_points&  convex_hull_;
        T_is_convex_hull_point(const T_points&  convex_hull) : convex_hull_(convex_hull)
        {}
        bool operator() (T_point  point)
        {
            return  std::find(convex_hull_.begin(), convex_hull_.end(), point) 
                        != convex_hull_.end();
        }
    };
    std::partition(points.begin(), points.end(), T_is_convex_hull_point(convex_hull_points));
    //Перебираем все точки выпуклой оболочки:
    for(T_points::const_iterator  it_A = points.begin();
        it_A != points.begin() + convex_hull_points.size(); ++it_A)
    {        
        T_coord  X_A = it_A->real();
        T_coord  Y_A = it_A->imag();
        //Перебираем все сочетания по две точки множества, исключая точку *it_A.
        for(T_points::const_iterator  it_B = points.begin();
            it_B != points.end(); ++it_B)
        {
            if(it_B == it_A) continue;
            T_coord  X_B = it_B->real();
            T_coord  Y_B = it_B->imag();
            T_point  vect_BA = vect(*it_B, *it_A);
            //Очевидно, что если в процессе вычисления расстояний какое-то расстояние H 
            //является на данный момент наибольшим, то достаточно для текущей точки A 
            //выпуклой оболочки вычислять расстояния только до прямых, проходящих 
            //через такие пары точек, что каждая из точек пары лежит от точки A дальше, чем H.
            //В данном случае для скорости сравниваем манхэттенское расстояние.
            if(less_equal_for_real(abs(X_B - X_A) + abs(Y_B - Y_A), H_max)) continue;           
 
            for(T_points::const_iterator  it_C = it_B + 1; it_C != points.end(); ++it_C)
            {
                if(it_C == it_A) continue;
                T_coord  X_C = it_C->real();
                T_coord  Y_C = it_C->imag();                
                if(less_equal_for_real(abs(X_C - X_A) + abs(Y_C - Y_A), H_max)) continue;
                
                //Находим расстояние от точки A до прямой BC:
                T_point  vect_BC = vect(*it_B, *it_C);
                T_coord  dist_A_BC = abs(det(vect_BA, vect_BC) / abs(vect_BC));
                if(dist_A_BC > H_max)
                {
                    H_max = dist_A_BC;
                    A = *it_A;
                    B = *it_B;
                    C = *it_C;
                }
            }        
        }
    }
    return  H_max;
}
/////////////////////////////////////////////////////////////////////////////////////
int main()
{
    std::locale::global(std::locale(""));    
 
    const int N_min = 3;
    const int N_max = 700;
    
    int n = 0;
    do
    {
        std::cout << "Число точек "
                  << N_min
                  << " <= n <= "
                  << N_max
                  << ": ";  
        std::cin >> n;
    }while(n < N_min 
           || N_max < n);
    
    T_points  points;
    std::cout << "Введите координаты "
              << n
              << " точек:"
              << std::endl;
 
    while(points.size() < static_cast<size_t>(n))
    {
        std::cout << std::endl
                  << "X"
                  << points.size() + 1
                  << " = ";
        T_coord  X = 0;
        std::cin >> X;
 
        std::cout << "Y"
                  << points.size() + 1
                  << " = ";
        T_coord  Y = 0;
        std::cin >> Y;
 
        T_point  point_cur = T_point(X, Y);
        if(   points.empty()
           || std::find(points.begin(), points.end(), point_cur) == points.end())
        {
            points.push_back(point_cur);    
        }
    }
    
    T_point  A;
    T_point  B;
    T_point  C;
    
    T_coord  dist_max = get_max_dist_from_point_to_line(points, A, B, C);
    std::cout << "В заданном множестве точек наибольшее расстояние от точки "
              << A 
              << " множества "
              << std::endl
              << "до прямой, проходящей через точки "
              << B 
              << " и "
              << C
              << " множества, равно "              
              << dist_max
              << std::endl;
}
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru