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

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

Восстановить пароль Регистрация
 
Yertugan
0 / 0 / 0
Регистрация: 11.12.2010
Сообщений: 6
15.12.2010, 04:43     Расстояние #1
На плоскостисвоими координатами задано N точек. Рассмотрим набор прямых, проведенных через все различные пары точек. Необходимоопределить наибольшеевозможноерасстояниеотлюбой заданной точки, до любой прямойпостроеннойподвумдругим точкам.
Задание
Напишите программу DIST, котораяпонабору точек плоскостивычисляет максимальноерасстояниеот точки до прямой.
Входные данные
Перваястрокавходного файлаDIST.DATсодержитединственное целое число – количество точек N
(3≤N≤700) заданных на плоскости. ДалееследуетNстрок, каждаяиз которых задает точку плоскостив формате “x y” (-5000≤x, y≤5000), x и y – целые числа. Никакие две точки не имеют одинаковых координат.

Выходные данные
Единственная строкавыходного файлаDIST.SOLдолжнасодержать наибольшеерасстояниеот однойиз заданных точек, до прямой,построенной на двух других точках, с точностью до 10-6. Ответдолжен быть записан в форматес точкой (<целая часть>.<дробная часть>)
Пример входных и выходных данных
DIST.DAT DIST.SOL
5
1 4
2 0
2 4
3 5
4 4 4.242641

уровнение прямой ax+b=y; далее:
(x2-x1)/(x-x1)=(y2-y1)/(y-y1);
a=(y2-y1)/(x2-x1);
b=-ax1+y1;

вот только я не пойму как прочертить линию от любой точки до прямой под 90 градусом?
Миниатюры
Расстояние  
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
15.12.2010, 04:43     Расстояние
Посмотрите здесь:

C++ Эвклидово расстояние.
C++ расстояние между шариками
Расстояние в дереве C++
Расстояние на графе C++
C++ расстояние от окружности к ломаной?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
accept
4838 / 3237 / 165
Регистрация: 10.12.2008
Сообщений: 10,682
15.12.2010, 05:09     Расстояние #2
wiki. расстояние от точки до прямой
Yertugan
0 / 0 / 0
Регистрация: 11.12.2010
Сообщений: 6
19.12.2010, 12:09  [ТС]     Расстояние #3
ОК! Понял, но у меня возник такой вопрос,
а что делать, если координаты двух точек
(x1,y1)=(-50,150)
(x2,y2)=(-50,-150)
то когда находим уравнение прямой то,
a=(y2-y1)/(x2-x1);
a=(-150-150)/(-50-(-50))
=> -300/0,
и что тогда?
accept
4838 / 3237 / 165
Регистрация: 10.12.2008
Сообщений: 10,682
20.12.2010, 03:05     Расстояние #4
вот с wiki
Миниатюры
Расстояние  
accept
4838 / 3237 / 165
Регистрация: 10.12.2008
Сообщений: 10,682
20.12.2010, 03:52     Расстояние #5
(x1,y1)=(-50,150)
(x2,y2)=(-50,-150)

это прямая x = -50
переносим x + 50 = 0
восстанавливаем x + 0 * y + 50 = 0

по формуле с wiki
(150 - (-150)) * x + (-50 - (-50)) * y + ((-50 * -150) - (-50 * 150)) = 0

300 * x + 0 * y + (7500 + 7500) = 0 | : 300

x + 0 * y + 50 = 0
Mr.X
Эксперт С++
 Аватар для Mr.X
2807 / 1583 / 248
Регистрация: 03.05.2010
Сообщений: 3,698
20.12.2010, 18:23     Расстояние #6
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;
}
Напильнег
480 / 120 / 10
Регистрация: 30.09.2010
Сообщений: 473
20.12.2010, 19:27     Расстояние #7
Цитата Сообщение от Yertugan Посмотреть сообщение
а что делать, если координаты двух точек
(x1,y1)=(-50,150)
(x2,y2)=(-50,-150)
то когда находим уравнение прямой то,
a=(y2-y1)/(x2-x1);
a=(-150-150)/(-50-(-50))
=> -300/0,
и что тогда?
Вбить себе в моск, что не все йогурты одинаково полезны для здоровья. Особенно Википедия.

Расстояние от точки до прямой на плоскости проще всего определить через кососкалярное произведение:
Код
|(x2-x1)(y-y1)-(y2-y1)(x-x1)|
-----------------------------
  sqrt((x2-x1)^2+(y2-y1)^2)
Удачи!
accept
4838 / 3237 / 165
Регистрация: 10.12.2008
Сообщений: 10,682
21.12.2010, 06:56     Расстояние #8
там на wiki есть расстояние от точки до прямой
просто модуль берётся
Миниатюры
Расстояние  
Напильнег
480 / 120 / 10
Регистрация: 30.09.2010
Сообщений: 473
21.12.2010, 11:39     Расстояние #9
Есть то оно есть, только вот не всем под силу ей воспользоваться, и это вполне естественно.

Собственно, моя формула представляет ее же, только до раскрытия скобок и приведения подобных членов (хренотени со знаком не понял, и разбираться не хочу), и в этом виде формула не только готова к употреблению, но и понятна, и даже не выводится, а просто выписывается за 30 секунд при необходимости. Надо только заметить, что она представляет собой скалярное произведение вектора (x1,y1)->(x,y) на нормированный перпендикуляр к вектору (x1,y1)->(x2,y2).

Не, ну если кто вращать вектора не умеет и скалярные произведения вычислять, то тогда в Википедию, а лучше сразу в морг <где тут свистящий смайлик?>
accept
4838 / 3237 / 165
Регистрация: 10.12.2008
Сообщений: 10,682
22.12.2010, 04:15     Расстояние #10
Цитата Сообщение от Напильнег
и в этом виде формула не только готова к употреблению
она для одной задачи, а общая формула для любой задачи
Напильнег
480 / 120 / 10
Регистрация: 30.09.2010
Сообщений: 473
22.12.2010, 12:21     Расстояние #11
То, что она называется общей, не значит, что она всему голова. На самом деле общее уравнение выводится из канонического, параметрического или (на плоскости) из того, что я написал, т.е. из способов задания, для которых влияние задающих элементов более прозрачно. На практике пользоваться общим уравнением не удобно. Ты можешь, взглянув на общее уравнение, сразу, без вычислений и прикидок, представить, как прямая проходит? Вот то-то.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
23.12.2010, 07:57     Расстояние
Еще ссылки по теме:

Расстояние между точками C++
Скорость первого автомобиля V1 км/ч, второго — V2 км/ч, расстояние между ними S км. Определить расстояние между ними через T часов, если автомобили пе C++
C++ Расстояние

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

Или воспользуйтесь поиском по форуму:
accept
4838 / 3237 / 165
Регистрация: 10.12.2008
Сообщений: 10,682
23.12.2010, 07:57     Расстояние #12
Цитата Сообщение от Напильнег
На практике пользоваться общим уравнением не удобно.
C
1
double point_to_line_dist(struct point *pt, struct sline *sl);
C
1
2
3
4
5
6
7
struct point {
    double x, y;
};
 
struct sline {
    double a, b, c;
};
его две точки
C
1
int points_to_line(struct sline *sl, struct point *pt1, struct point *pt2);
итого
C
1
2
3
4
5
6
7
8
9
    struct sline sl;
    struct point a = { 0.5, 0.5 };
    struct point b = { 0.5, 1.5 };
    struct point n = { 1.0, 1.0 };
 
    if (points_to_line(&sl, &a, &b) == 0) {
        double dist = point_to_line_dist(&n, &sl);
        printf("%f" "\n", dist);
    }
то есть можно не писать десять функций, чтобы найти расстояние от точки до прямой

Цитата Сообщение от Напильнег
Ты можешь, взглянув на общее уравнение, сразу, без вычислений и прикидок, представить, как прямая проходит?
для чего ?

2*x + 4*y - 7 = 0
C
1
2
3
4
5
6
7
8
9
10
11
    struct sline sl;
 
    sl.a = 2;
    sl.b = 4;
    sl.c = -7;
 
    {
        struct point n = { 0.5, 0.5 };
        double dist = point_to_line_dist(&n, &sl);
        printf("%f" "\n", dist);
    }
Yandex
Объявления
23.12.2010, 07:57     Расстояние
Ответ Создать тему
Опции темы

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