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

3 взаимно пересекающиеся окружности - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 10, средняя оценка - 4.70
Милок
0 / 0 / 0
Регистрация: 25.06.2010
Сообщений: 21
07.07.2010, 14:47     3 взаимно пересекающиеся окружности #1
1. Окружность на плоскости может быть задана координатами x, y ее центра и радиусом r. Пусть даны соответствующие характеристики нескольких окружностей: x1, y1, r1, x2, y2, r2,…, xn, yn, rn.
а) Определить, имеются ли среди этих окружностей три взаимно пересекающиеся .
б) Найти среди этих окружностей все уединенные окружности, т.е. такие, которые не имеют общих точек ни с одной из остальных окружностей, не лежат целиком внутри и не заключают внутри себя какой-либо из остальных окружностей.


P.S. это последняя задача. Кто сможет, помогите.Если нетрудно, то всю задачу.....
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Mr.X
Эксперт С++
 Аватар для Mr.X
2798 / 1574 / 246
Регистрация: 03.05.2010
Сообщений: 3,655
08.07.2010, 01:40     3 взаимно пересекающиеся окружности #2
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
////////////////////////////////////////////////////////////////////////////////////
//1. Окружность на плоскости может быть задана координатами x, y ее центра 
//и радиусом r. Пусть даны соответствующие характеристики нескольких окружностей: 
//x1, y1, r1, x2, y2, r2,…, xn, yn, rn.
//а) Определить, имеются ли среди этих окружностей три взаимно пересекающиеся .
//б) Найти среди этих окружностей все уединенные окружности, т.е. такие, которые 
//не имеют общих точек ни с одной из остальных окружностей, не лежат целиком 
//внутри и не заключают внутри себя какой-либо из остальных окружностей.
////////////////////////////////////////////////////////////////////////////////////
#include <iostream>
#include <complex>
#include <vector>
#include <algorithm>
 
typedef double                 T_coord;
typedef std::complex<T_coord>  T_center;
enum T_okr_rasp
{
    SAMA_S_SOBOJ = 0,
    SNARUJI,
    PERESEK,
    VNUTRI
};
class T_okr
{
    T_center  center_;    
    T_coord  radius_;
public:
    T_okr
        (
            T_coord  X       = 0, 
            T_coord  Y       = 0, 
            T_coord  radius  = 0
        ) : center_(X, Y), radius_(radius)
    {}
 
    T_okr_rasp  get_vzaimn_rasp(const T_okr&  okr) const
    {
        T_coord  center_dist      = abs(center_ - okr.center_);
        T_coord  radius_sum       = radius_ + okr.radius_;
        T_coord  radius_razn_abs  = abs(radius_ - okr.radius_);
        if(radius_sum < center_dist)
        {
            return  SNARUJI;
        }        
        if(radius_razn_abs > center_dist)
        {
            return  VNUTRI;
        }
        return  PERESEK;
    }
};
typedef std::vector<T_okr>  T_okrujnosti;
 
void  print_3_peresek_and_otdeln_okr(const T_okrujnosti&  okrujnosti) 
{
    typedef std::vector<T_okr_rasp>  T_rasp_row;
    typedef std::vector<T_rasp_row>  T_rasp_matr;
    class T_rasp_tabl
    {
        int          dim_;
        T_rasp_matr  rasp_matr_;
    public:
        T_rasp_tabl(const T_okrujnosti&  okrujnosti) 
            :dim_(okrujnosti.size()), rasp_matr_(dim_, T_rasp_row(dim_))
        {
            for(int i = 0; i < dim_; ++i)
            {
                for(int j = 0; j < dim_; ++j)
                {                    
                    if(i == j) continue;
                    rasp_matr_[i][j] 
                        = okrujnosti[i].get_vzaimn_rasp(okrujnosti[j]);                    
                }
            }        
        }
        //----------------------------------------------------------------------
        T_okr_rasp  operator() (int i, int j) const
        {
            return  rasp_matr_[i][j]; 
        }
        //----------------------------------------------------------------------
        T_okr_rasp&  operator() (int i, int j) 
        {
            return  rasp_matr_[i][j]; 
        }
        //----------------------------------------------------------------------
        void  print_3_vzaimno_peresek_okr() const
        {            
            const int VZAIM_PERESEK_MIN = 3;            
            for(int i = 0; i < dim_; ++i)
            {
                int count_peresek 
                    = std::count(rasp_matr_[i].begin(), 
                                 rasp_matr_[i].end(), PERESEK);                
                if(count_peresek < VZAIM_PERESEK_MIN - 1) continue;
                int perv_okr_num = i;
                for(int j = 0; j < count_peresek - 1; ++j)
                {
                    perv_okr_num 
                        = std::find(rasp_matr_[i].begin() + perv_okr_num, 
                                    rasp_matr_[i].end(), PERESEK)
                        - rasp_matr_[i].begin() + 1;
                    int vtor_okr_num = perv_okr_num;
                    for(int k = 0; k < count_peresek - 1 - j; ++k)
                    {
                        vtor_okr_num 
                            = std::find(rasp_matr_[i].begin() + vtor_okr_num, 
                                        rasp_matr_[i].end(), PERESEK)
                            - rasp_matr_[i].begin() + 1;
                        if(rasp_matr_[perv_okr_num - 1][vtor_okr_num - 1] == PERESEK)
                        {
                            std::cout << "Взаимно пересекаются "
                                      << VZAIM_PERESEK_MIN
                                      <<" окружности: "
                                      << i + 1
                                      << ", "
                                      << perv_okr_num 
                                      << ", "
                                      << vtor_okr_num
                                      << "."
                                      << std::endl;
                            return;
                        }//if(rasp_matr_[perv_okr_num - 1][vtor_okr_num - 1] == PERESEK)
                    }//for(int k = 0; k < count_peresek - 1 - j; ++k)
                }//for(int j = 0; j < count_peresek - 1; ++j)
            }//for(int i = 0; i < dim_; ++i)
            std::cout << "Среди заданных окружностей нет "
                      << VZAIM_PERESEK_MIN
                      << " взаимно пересекающихся."
                      << std::endl;          
        }
        //----------------------------------------------------------------------
        void  print_ued_okr() const
        {
            struct  T_is_ued_okr
            {
                int row_dim_;
                T_is_ued_okr(int row_dim) : row_dim_(row_dim)
                {}
                bool operator() (const T_rasp_row&  rasp_row)
                {
                    return  std::count(rasp_row.begin(), 
                              rasp_row.end(), SNARUJI) == row_dim_ - 1;
                }
            };
            int count = std::count_if(rasp_matr_.begin(), 
                                      rasp_matr_.end(), T_is_ued_okr(dim_));
            if(count == 0)
            {
                std::cout << "Уединенных окружностей нет."
                          << std::endl;
            }
            else
            {
                std::cout << "Уединенные окружности: ";
                int cur_okr_num = 0;
                for(int i = 0; i < count; ++i)
                {                    
                    cur_okr_num =
                    std::find_if(rasp_matr_.begin() + cur_okr_num, 
                                    rasp_matr_.end(), T_is_ued_okr(dim_))
                       - rasp_matr_.begin() + 1;
                    std::cout << cur_okr_num;
                    if(i == count - 1)
                    {
                        std::cout << "."
                                  << std::endl;
                    }
                    else
                    {
                        std::cout << ", ";
                    }
                }//for(int i = 0; i < count; ++i)            
            }//if(count == 0)...else
        }
    };
    T_rasp_tabl  rasp_tabl(okrujnosti);
    rasp_tabl.print_3_vzaimno_peresek_okr();
    rasp_tabl.print_ued_okr();   
}
 
int main()
{
    std::locale::global(std::locale(""));
    std::cout << "Введите количество окружностей: ";
    int n;
    std::cin >> n;
    std::cout << "Введите координаты и радиус каждой окружности:";
    T_okrujnosti  okrujnosti;
    for(int i = 0; i < n; ++i)
    {
        std::cout << std::endl
                  << "X"
                  << i + 1
                  << " = ";
        int x;
        std::cin >> x;
 
        std::cout << "Y"
                  << i + 1
                  << " = ";
        int y;
        std::cin >> y;
 
        std::cout << "R"
                  << i + 1
                  << " = ";
        int r;
        std::cin >> r;
        okrujnosti.push_back(T_okr(x, y, r));        
    }
    print_3_peresek_and_otdeln_okr(okrujnosti);
    return 0;
}
Милок
0 / 0 / 0
Регистрация: 25.06.2010
Сообщений: 21
08.07.2010, 08:39  [ТС]     3 взаимно пересекающиеся окружности #3
T_coord radius_razn_abs = abs(radius_ - okr.radius_);
При компиляции выходит что на этой строке ошибка.....И дальше он работать отказывается....Что делать?
Nameless One
Эксперт С++
 Аватар для Nameless One
5753 / 3402 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
08.07.2010, 09:29     3 взаимно пересекающиеся окружности #4
Что за ошибка? Попробуй подключить <cmath>
Милок
0 / 0 / 0
Регистрация: 25.06.2010
Сообщений: 21
08.07.2010, 09:51  [ТС]     3 взаимно пересекающиеся окружности #5
In member function `T_okr_rasp T_okr::get_vzaimn_rasp(const T_okr&) const':
41 [Warning] passing `double' for converting 1 of `int abs(int)'
In member function `void print_3_peresek_and_otdeln_okr(const T_okrujnosti&)::T_rasp_tabl:rint_ued_okr() const':

148 no matching function for call to `count_if(__gnu_cxx::__normal_iterator<const print_3_peresek_and_otdeln_okr(const T_okrujnosti&)::T_rasp_row*, std::vector<print_3_peresek_and_otdeln_okr(const T_okrujnosti&)::T_rasp_row, std::allocator<print_3_peresek_and_otdeln_okr(const T_okrujnosti&)::T_rasp_row> > >, __gnu_cxx::__normal_iterator<const print_3_peresek_and_otdeln_okr(const T_okrujnosti&)::T_rasp_row*, std::vector<print_3_peresek_and_otdeln_okr(const T_okrujnosti&)::T_rasp_row, std::allocator<print_3_peresek_and_otdeln_okr(const T_okrujnosti&)::T_rasp_row> > >, print_3_peresek_and_otdeln_okr(const T_okrujnosti&)::T_rasp_tabl:rint_ued_okr() const::T_is_ued_okr)'

162 no matching function for call to `find_if(__gnu_cxx::__normal_iterator<const print_3_peresek_and_otdeln_okr(const T_okrujnosti&)::T_rasp_row*, std::vector<print_3_peresek_and_otdeln_okr(const T_okrujnosti&)::T_rasp_row, std::allocator<print_3_peresek_and_otdeln_okr(const T_okrujnosti&)::T_rasp_row> > >, __gnu_cxx::__normal_iterator<const print_3_peresek_and_otdeln_okr(const T_okrujnosti&)::T_rasp_row*, std::vector<print_3_peresek_and_otdeln_okr(const T_okrujnosti&)::T_rasp_row, std::allocator<print_3_peresek_and_otdeln_okr(const T_okrujnosti&)::T_rasp_row> > >, print_3_peresek_and_otdeln_okr(const T_okrujnosti&)::T_rasp_tabl:rint_ued_okr() const::T_is_ued_okr)'

А как подключить <cmath>?
Nameless One
Эксперт С++
 Аватар для Nameless One
5753 / 3402 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
08.07.2010, 09:53     3 взаимно пересекающиеся окружности #6
Цитата Сообщение от Милок Посмотреть сообщение
А как подключить <cmath>?
C++
1
#include <cmath>
Милок
0 / 0 / 0
Регистрация: 25.06.2010
Сообщений: 21
08.07.2010, 09:57  [ТС]     3 взаимно пересекающиеся окружности #7
Спс, только не помогло. Он также показывает....
Nameless One
Эксперт С++
 Аватар для Nameless One
5753 / 3402 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
08.07.2010, 10:11     3 взаимно пересекающиеся окружности #8
У меня все нормально компилируется. А с чего ты взял, что ошибка у тебя на строке "T_coord radius_razn_abs = abs(radius_ - okr.radius_);"? Судя по всему, у тебя проблема с алгоритмами count_if и find_if.
Милок
0 / 0 / 0
Регистрация: 25.06.2010
Сообщений: 21
08.07.2010, 10:18  [ТС]     3 взаимно пересекающиеся окружности #9
При компиляции, он указывает что на этой строке ошибка....и оказывается дальше работать....
Nameless One
Эксперт С++
 Аватар для Nameless One
5753 / 3402 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
08.07.2010, 10:24     3 взаимно пересекающиеся окружности #10
Цитата Сообщение от Милок Посмотреть сообщение
148 no matching function for call to `count_if(
Цитата Сообщение от Милок Посмотреть сообщение
162 no matching function for call to `find_if(
А не из-за этого?
Милок
0 / 0 / 0
Регистрация: 25.06.2010
Сообщений: 21
08.07.2010, 11:49  [ТС]     3 взаимно пересекающиеся окружности #11
Да, функции вызова не соответствуют.......

Добавлено через 1 час 19 минут
а как исправить этот все?
Nameless One
Эксперт С++
 Аватар для Nameless One
5753 / 3402 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
08.07.2010, 11:52     3 взаимно пересекающиеся окружности #12
Ну, я думаю, все дело в твоем компиляторе, потому что у меня все работает. Проверь, может быть у тебя некоторые заголовочные файлы называются по-другому.
Милок
0 / 0 / 0
Регистрация: 25.06.2010
Сообщений: 21
08.07.2010, 21:17  [ТС]     3 взаимно пересекающиеся окружности #13
Да нет, все также.........=(((((((

Добавлено через 7 часов 21 минуту
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
#include <iostream>
#include <complex>
#include <vector>
#include <algorithm>
#include <cmath>
 
typedef double                 T_coord;
typedef std::complex<T_coord>  T_center;
enum T_okr_rasp
{
    SAMA_S_SOBOJ = 0,
    SNARUJI,
    PERESEK,
    VNUTRI
};
class T_okr
{
    T_center  center_;    
    T_coord  radius_;
public:
    T_okr
        (
            T_coord  X       = 0, 
            T_coord  Y       = 0, 
            T_coord  radius  = 0
        ) : center_(X, Y), radius_(radius)
    {}
 
    T_okr_rasp  get_vzaimn_rasp(const T_okr&  okr) const
    {
        T_coord  center_dist      = abs(center_ - okr.center_);
        T_coord  radius_sum       = radius_ + okr.radius_;
        T_coord  radius_razn_abs  = abs(radius_ - okr.radius_);
        if(radius_sum < center_dist)
        {
            return  SNARUJI;
        }        
        if(radius_razn_abs > center_dist)
        {
            return  VNUTRI;
        }
        return  PERESEK;
    }
};
typedef std::vector<T_okr>  T_okrujnosti;
 
void  print_3_peresek_and_otdeln_okr(const T_okrujnosti&  okrujnosti) 
{
    typedef std::vector<T_okr_rasp>  T_rasp_row;
    typedef std::vector<T_rasp_row>  T_rasp_matr;
    class T_rasp_tabl
    {
        int          dim_;
        T_rasp_matr  rasp_matr_;
    public:
        T_rasp_tabl(const T_okrujnosti&  okrujnosti) 
            :dim_(okrujnosti.size()), rasp_matr_(dim_, T_rasp_row(dim_))
        {
            for(int i = 0; i < dim_; ++i)
            {
                for(int j = 0; j < dim_; ++j)
                {                    
                    if(i == j) continue;
                    rasp_matr_[i][j] 
                        = okrujnosti[i].get_vzaimn_rasp(okrujnosti[j]);                    
                }
            }        
        }
        //----------------------------------------------------------------------
        T_okr_rasp  operator() (int i, int j) const
        {
            return  rasp_matr_[i][j]; 
        }
        //----------------------------------------------------------------------
        T_okr_rasp&  operator() (int i, int j) 
        {
            return  rasp_matr_[i][j]; 
        }
        //----------------------------------------------------------------------
        void  print_3_vzaimno_peresek_okr() const
        {            
            const int VZAIM_PERESEK_MIN = 3;            
            for(int i = 0; i < dim_; ++i)
            {
                int count_peresek 
                    = std::count(rasp_matr_[i].begin(), 
                                 rasp_matr_[i].end(), PERESEK);                
                if(count_peresek < VZAIM_PERESEK_MIN - 1) continue;
                int perv_okr_num = i;
                for(int j = 0; j < count_peresek - 1; ++j)
                {
                    perv_okr_num 
                        = std::find(rasp_matr_[i].begin() + perv_okr_num, 
                                    rasp_matr_[i].end(), PERESEK)
                        - rasp_matr_[i].begin() + 1;
                    int vtor_okr_num = perv_okr_num;
                    for(int k = 0; k < count_peresek - 1 - j; ++k)
                    {
                        vtor_okr_num 
                            = std::find(rasp_matr_[i].begin() + vtor_okr_num, 
                                        rasp_matr_[i].end(), PERESEK)
                            - rasp_matr_[i].begin() + 1;
                        if(rasp_matr_[perv_okr_num - 1][vtor_okr_num - 1] == PERESEK)
                        {
                            std::cout << "Взаимно пересекаются "
                                      << VZAIM_PERESEK_MIN
                                      <<" окружности: "
                                      << i + 1
                                      << ", "
                                      << perv_okr_num 
                                      << ", "
                                      << vtor_okr_num
                                      << "."
                                      << std::endl;
                            return;
                        }//if(rasp_matr_[perv_okr_num - 1][vtor_okr_num - 1] == PERESEK)
                    }//for(int k = 0; k < count_peresek - 1 - j; ++k)
                }//for(int j = 0; j < count_peresek - 1; ++j)
            }//for(int i = 0; i < dim_; ++i)
            std::cout << "Среди заданных окружностей нет "
                      << VZAIM_PERESEK_MIN
                      << " взаимно пересекающихся."
                      << std::endl;          
        }
        //----------------------------------------------------------------------
        void  print_ued_okr() const
        {
            struct  T_is_ued_okr
            {
                int row_dim_;
                T_is_ued_okr(int row_dim) : row_dim_(row_dim)
                {}
                bool operator() (const T_rasp_row&  rasp_row)
                {
                    return  std::count(rasp_row.begin(), 
                              rasp_row.end(), SNARUJI) == row_dim_ - 1;
                }
            };
            int count = std::count_if(rasp_matr_.begin(), 
                                      rasp_matr_.end(), T_is_ued_okr(dim_));
            if(count == 0)
            {
                std::cout << "Уединенных окружностей нет."
                          << std::endl;
            }
            else
            {
                std::cout << "Уединенные окружности: ";
                int cur_okr_num = 0;
                for(int i = 0; i < count; ++i)
                {                    
                    cur_okr_num =
                    std::find_if(rasp_matr_.begin() + cur_okr_num, 
                                    rasp_matr_.end(), T_is_ued_okr(dim_))
                       - rasp_matr_.begin() + 1;
                    std::cout << cur_okr_num;
                    if(i == count - 1)
                    {
                        std::cout << "."
                                  << std::endl;
                    }
                    else
                    {
                        std::cout << ", ";
                    }
                }//for(int i = 0; i < count; ++i)            
            }//if(count == 0)...else
        }
    };
    T_rasp_tabl  rasp_tabl(okrujnosti);
    rasp_tabl.print_3_vzaimno_peresek_okr();
    rasp_tabl.print_ued_okr();   
}
 
int main()
{
    std::locale::global(std::locale(""));
    std::cout << "Введите количество окружностей: ";
    int n;
    std::cin >> n;
    std::cout << "Введите координаты и радиус каждой окружности:";
    T_okrujnosti  okrujnosti;
    for(int i = 0; i < n; ++i)
    {
        std::cout << std::endl
                  << "X"
                  << i + 1
                  << " = ";
        int x;
        std::cin >> x;
 
        std::cout << "Y"
                  << i + 1
                  << " = ";
        int y;
        std::cin >> y;
 
        std::cout << "R"
                  << i + 1
                  << " = ";
        int r;
        std::cin >> r;
        okrujnosti.push_back(T_okr(x, y, r));        
    }
    print_3_peresek_and_otdeln_okr(okrujnosti);
    return 0;
}
Все же ведь так. И как мне его сдать?.....
Nameless One
Эксперт С++
 Аватар для Nameless One
5753 / 3402 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
09.07.2010, 04:56     3 взаимно пересекающиеся окружности #14
Цитата Сообщение от Милок Посмотреть сообщение
Все же ведь так. И как мне его сдать?.....
Программа работает. Попробуй другой компилятор.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
09.07.2010, 08:42     3 взаимно пересекающиеся окружности
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
Милок
0 / 0 / 0
Регистрация: 25.06.2010
Сообщений: 21
09.07.2010, 08:42  [ТС]     3 взаимно пересекающиеся окружности #15
Ладно спасибо всем....
Yandex
Объявления
09.07.2010, 08:42     3 взаимно пересекающиеся окружности
Ответ Создать тему
Опции темы

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