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

C для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.89
Enies Lobby
0 / 0 / 0
Регистрация: 11.07.2012
Сообщений: 8
#1

Найти координаты центра и радиус минимального круга, который содержит все данные точки - C (СИ)

16.12.2012, 19:25. Просмотров 1284. Ответов 0
Метки нет (Все метки)

Всем привет! Помогите, пожалуйста)) Программу я написал, но она не во всех случаях работает((

Дано множество точек. Записать через пробел в выходной файл координаты центра и радиус минимального круга, который содержит все эти точки.

Всю задачу написал для понятности. Что я делаю: Нахожу "выпуклую оболочку ( краевые точки )", Потом сначало беру все возможные варианты по две точки ( беру как радиус растояние между ними попалам, а центр - середина этого отрезка ), потом беру по три точки ( строю треугольник и нахожу центр описаной вокруг него окружности ).
В чем ошибка: 5 0 0 6 0 6 4 3 20 4 0 при таких входных файлах ответ не верный!

Прошу помочь с нахождением центра описанной окружности, думаю проблема в ней! ( Хотя на простых примерах она работает отлично - это когда ввожу прямоугольный треугольник )

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
sPoint_30_5_06 task_30_5_06_define_center_triangle ( sPoint_30_5_06 pointA, sPoint_30_5_06 pointB, sPoint_30_5_06 pointC, double *s )
{       
 
   double x1 = pointA.x;
   double y1 = pointA.y;
   double x2 = pointB.x;
   double y2 = pointB.y;
   double x3 = pointC.x;
   double y3 = pointC.y;
   double y0;
   double x0;
 
   sPoint_30_5_06 center_triangle;
   
   *s = 0.5 * abs( x1*( y2 - y3 ) - y1*( x2 - x3 ) + x2*y3 - y2*x3 );
 
   if ( x1 == x2 )
   {
       double k = (y3 - y2)/(x3 - x2); 
       y0 = ( y1 + y2 )/2;
       x0 = k*(y2 + y3)/2 + (y2 + y3)/2 - k*(y2+y1)/2;
       center_triangle.x = x0;
       center_triangle.y = y0;
       return center_triangle;
   }
 
  if ( x2 == x3 )
   {
       double k = (y3 - y1)/(x3 - x1); 
       y0 = ( y2 + y3 )/2;
       x0 = k*(y1 + y3)/2 + (y1 + y3)/2 - k*(y2 + y3)/2;
       center_triangle.x = x0;
       center_triangle.y = y0;
       return center_triangle;
 
   }
    
   if ( x1 == x3 )
   {
       double k = (y3 - y2)/(x3 - x2); 
       y0 = ( y1 + y2 )/2;
       x0 = k*(y2 + y3)/2 + (y2 + y3)/2 - k*(y2+y1)/2;
       center_triangle.x = x0;
       center_triangle.y = y0;
       return center_triangle;
 
   }
 
    y0 = ( (x2*x2 + y2*y2 - x1*x1 - y1*y1)*(x3-x1) 
        - (x3*x3 + y3*y3 - x1*x1 -y1*y1)*(x2-x1) ) / ( 2*( (y1-y3)*(x2-x1) - (y1-y2)*(x3-x1) ) );
    x0 = ( (x2*x2 + y2*y2 - x1*x1 -y1*y1 + (2*y1 - 2*y2)*y0) ) / (2*x2 - 2*x1);
    
    center_triangle.x = x0;
    center_triangle.y = y0;
 
return center_triangle;
}
 
 
int task_30_5_06_check_radius ( sMUnited_30_5_06 setOfPoints, sPoint_30_5_06 center, double lengthAB )
{
    double sqrtemp_radius;
    double radius = lengthAB/4;
    int i = 0;
    for ( i = 0; i < setOfPoints.numb; i ++ )
    {
        sqrtemp_radius = ( setOfPoints.dot_arr[i].x - center.x )*( setOfPoints.dot_arr[i].x - center.x )
            + ( setOfPoints.dot_arr[i].y - center.y )*( setOfPoints.dot_arr[i].y - center.y );
        if ( sqrtemp_radius > radius ) return -666; 
    }
 
return 0;
}
Что к чему: setOfPoints.dot_arr[i] - Исходный массив точек, lenthAB - квадрат расстояния между центром окружности и используемой точки!

Помоги очень прошууууу уже неделю маюсь с ней(((

Если у кого-нибудь есть работающий код нахождения цетра опсанной окружности буду очень рад !

Весь файлик целиком:
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
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
 
 
typedef
    struct sPoint_30_5_06_
    {
        double x;
        double y;
 
    }sPoint_30_5_06;
 
typedef
    struct sMUnited_30_5_06_
    {
        sPoint_30_5_06 *dot_arr;
        sPoint_30_5_06 *cov_arr;
        int numb;
        int numbOfCover;
 
    }sMUnited_30_5_06;
 
double task_30_5_06_sqrlength ( sPoint_30_5_06 pointA, sPoint_30_5_06 pointB )
{
    double result;
    result = ( pointB.x - pointA.x )*( pointB.x - pointA.x ) + ( pointB.y - pointA.y )*( pointB.y - pointA.y );
 
return result;
}
 
 
double task_30_5_06_radius_ofTriangle ( sPoint_30_5_06 pointA, sPoint_30_5_06 center_ofTriangle )
{
    double R;
 
   R = sqrt(( pointA.x - center_ofTriangle.x )*( pointA.x - center_ofTriangle.x ) + 
       ( pointA.y - center_ofTriangle.y )*( pointA.y - center_ofTriangle.y ));
 
return R;
}
 
sPoint_30_5_06 task_30_5_06_define_center_triangle ( sPoint_30_5_06 pointA, sPoint_30_5_06 pointB, sPoint_30_5_06 pointC, double *s )
{       
 
   double x1 = pointA.x;
   double y1 = pointA.y;
   double x2 = pointB.x;
   double y2 = pointB.y;
   double x3 = pointC.x;
   double y3 = pointC.y;
   double y0;
   double x0;
 
   sPoint_30_5_06 center_triangle;
   
   *s = 0.5 * abs( x1*( y2 - y3 ) - y1*( x2 - x3 ) + x2*y3 - y2*x3 );
 
   if ( x1 == x2 )
   {
       double k = (y3 - y2)/(x3 - x2); 
       y0 = ( y1 + y2 )/2;
       x0 = k*(y2 + y3)/2 + (y2 + y3)/2 - k*(y2+y1)/2;
       center_triangle.x = x0;
       center_triangle.y = y0;
       return center_triangle;
   }
 
  if ( x2 == x3 )
   {
       double k = (y3 - y1)/(x3 - x1); 
       y0 = ( y2 + y3 )/2;
       x0 = k*(y1 + y3)/2 + (y1 + y3)/2 - k*(y2 + y3)/2;
       center_triangle.x = x0;
       center_triangle.y = y0;
       return center_triangle;
 
   }
    
   if ( x1 == x3 )
   {
       double k = (y3 - y2)/(x3 - x2); 
       y0 = ( y1 + y2 )/2;
       x0 = k*(y2 + y3)/2 + (y2 + y3)/2 - k*(y2+y1)/2;
       center_triangle.x = x0;
       center_triangle.y = y0;
       return center_triangle;
 
   }
 
    y0 = ( (x2*x2 + y2*y2 - x1*x1 - y1*y1)*(x3-x1) 
        - (x3*x3 + y3*y3 - x1*x1 -y1*y1)*(x2-x1) ) / ( 2*( (y1-y3)*(x2-x1) - (y1-y2)*(x3-x1) ) );
    x0 = ( (x2*x2 + y2*y2 - x1*x1 -y1*y1 + (2*y1 - 2*y2)*y0) ) / (2*x2 - 2*x1);
    
    center_triangle.x = x0;
    center_triangle.y = y0;
 
return center_triangle;
}
 
 
int task_30_5_06_check_radius ( sMUnited_30_5_06 setOfPoints, sPoint_30_5_06 center, double lengthAB )
{
    double sqrtemp_radius;
    double radius = lengthAB/4;
    int i = 0;
    for ( i = 0; i < setOfPoints.numb; i ++ )
    {
        sqrtemp_radius = ( setOfPoints.dot_arr[i].x - center.x )*( setOfPoints.dot_arr[i].x - center.x )
            + ( setOfPoints.dot_arr[i].y - center.y )*( setOfPoints.dot_arr[i].y - center.y );
        if ( sqrtemp_radius > radius ) return -666; 
    }
 
return 0;
}
 
int task_30_5_06_vect_mult ( sPoint_30_5_06 pointA, sPoint_30_5_06 pointB, sPoint_30_5_06 pointC, sPoint_30_5_06 pointD )
{
    double result;
    result = ( pointB.x - pointA.x )*( pointD.y - pointC.y ) - ( pointD.x - pointC.x )*( pointB.y - pointA.y );   
 
return result;
}
 
int task_30_5_06_define_cover ( sMUnited_30_5_06 setOfPoints, int *number_ofCover )
{
 
    int m = 1, i = 0;
    for ( i = 1; i < setOfPoints.numb; i ++ )
    {
        if ( setOfPoints.dot_arr[i].y < setOfPoints.dot_arr[m].y )
            {
             m = i;
            }
             else 
                 if ((setOfPoints.dot_arr[i].y == setOfPoints.dot_arr[m].y) && (setOfPoints.dot_arr[i].x > setOfPoints.dot_arr[m].x))
                 {
                     m = i;
                 }
    }
 
    setOfPoints.cov_arr[0].x = setOfPoints.dot_arr[m].x;
    setOfPoints.cov_arr[0].y = setOfPoints.dot_arr[m].y;
 
    setOfPoints.dot_arr[m].x = setOfPoints.dot_arr[0].x;
    setOfPoints.dot_arr[m].y = setOfPoints.dot_arr[0].y;
 
    setOfPoints.dot_arr[0].x = setOfPoints.cov_arr[0].x;
    setOfPoints.dot_arr[0].y = setOfPoints.cov_arr[0].y;
 
     int k = 0 , min = 1, j = 0;
     
     do
     {
        for( j = 1; j < setOfPoints.numb; j ++ )
        if ( 
        (task_30_5_06_vect_mult( setOfPoints.cov_arr[k], setOfPoints.dot_arr[min], setOfPoints.cov_arr[k], setOfPoints.dot_arr[j] ) < 0) || 
        ((task_30_5_06_vect_mult( setOfPoints.cov_arr[k], setOfPoints.dot_arr[min], setOfPoints.cov_arr[k], setOfPoints.dot_arr[j] ) == 0) 
        && (task_30_5_06_sqrlength( setOfPoints.cov_arr[k], setOfPoints.dot_arr[min] ) < task_30_5_06_sqrlength( setOfPoints.cov_arr[k], setOfPoints.dot_arr[j] ))))
            {
                min = j;
            }
                    k = k + 1;
                    setOfPoints.cov_arr[k] = setOfPoints.dot_arr[min];
                    min = 0;
 
        if (  setOfPoints.cov_arr[k].x ==  setOfPoints.cov_arr[0].x && setOfPoints.cov_arr[k].y ==  setOfPoints.cov_arr[0].y ) 
            break;
    }
    while (1);
    *number_ofCover = k;
 
return 0;
}
 
 
int task_30_5_06_define_radius ( sMUnited_30_5_06 setOfPoints, int number_ofCover, sPoint_30_5_06 *result_center, double *result_radius )
{
    int i = 0, j = 0, Q = 0;
    double lengthAB, minlength = -666;
    sPoint_30_5_06 center;
 
    *result_radius = -666;
 
    for ( i = 0; i < number_ofCover; i ++ )
    {
        for ( j = 0; j < number_ofCover; j ++ )
        {
            if ( i != j )
            {
                lengthAB = (double) task_30_5_06_sqrlength( setOfPoints.cov_arr[i], setOfPoints.cov_arr[j] );
                center.x = ( setOfPoints.cov_arr[i].x + setOfPoints.cov_arr[j].x ) / 2;
                center.y = ( setOfPoints.cov_arr[i].y + setOfPoints.cov_arr[j].y ) / 2;
                if ( task_30_5_06_check_radius( setOfPoints, center, lengthAB ) == 0 ) 
                { 
                    if ( lengthAB < minlength || minlength == -666 ) 
                    {
                        minlength = lengthAB;
                        result_center->x = center.x;
                        result_center->y = center.y;
                    }
                }
            }
 
        }      
    }
 
    if ( minlength != -666 )
    {
        *result_radius = sqrt( minlength )/2;
        return 0;
    }
 
 
    sPoint_30_5_06 center_ofTriangle;
    double s = 0.0, R;
 
    for ( i = 0; i < setOfPoints.numb; i ++ )
        for ( j = 0; j < setOfPoints.numb; j++ )
            for ( Q = 0; Q < setOfPoints.numb; Q ++ )
            {
          
                if ( ( i != j) && ( j != Q) && ( Q != j) && ( Q != i ) )
                {
                center_ofTriangle = task_30_5_06_define_center_triangle( setOfPoints.cov_arr[i], setOfPoints.cov_arr[j], setOfPoints.cov_arr[Q], &s );
                R = task_30_5_06_radius_ofTriangle( setOfPoints.cov_arr[i], center_ofTriangle );
                
                if ( (task_30_5_06_check_radius( setOfPoints, center_ofTriangle, (2*R)*(2*R) )) == 0 ) 
                { 
                    if ( (((2*R)*(2*R)) < minlength) || (minlength == -666) ) 
                    {
                        minlength = (2*R)*(2*R);
                        result_center->x = center_ofTriangle.x;
                        result_center->y = center_ofTriangle.y;
                    }
                }   
                }  
                
               
            }
    
    
    if ( minlength != -666 )
    {
        *result_radius = sqrt( minlength )/2;
        return 0;
    }
 
 
 
return 0;
}
 
 
int task_30_5_06 ( char * filename )
{
 
    // Open file
 
    FILE * fileread = fopen( filename, "r" );
    if ( fileread == NULL ) return -666;
 
    sMUnited_30_5_06 setOfPoints;
 
    if ( fscanf( fileread, "%d", &(setOfPoints.numb) ) == 0 ) return -666;
    setOfPoints.dot_arr = ( sPoint_30_5_06 * ) malloc ( sizeof ( sPoint_30_5_06 ) * setOfPoints.numb );
    setOfPoints.cov_arr = ( sPoint_30_5_06 * ) malloc ( sizeof ( sPoint_30_5_06 ) * setOfPoints.numb );
    
    int i = 0, number_ofCover;
    for ( i = 0; i < setOfPoints.numb; i ++ ) 
    {
         setOfPoints.cov_arr[i].x = 0;
         setOfPoints.cov_arr[i].y = 0;
    }
 
    for ( i = 0; i < setOfPoints.numb; i ++ )
        {
            fscanf( fileread, "%lf", &(setOfPoints.dot_arr[i].x) );
            fscanf( fileread, "%lf", &(setOfPoints.dot_arr[i].y) );
        }
    fclose( fileread );
    
    sPoint_30_5_06 result_center;
    double result_radius = 0.0;
 
/////////////////////////////////////////////////////////////////////////////////////////////////////
    task_30_5_06_define_cover ( setOfPoints, &number_ofCover );
    task_30_5_06_define_radius ( setOfPoints, number_ofCover, &result_center, &result_radius );
 
/////////////////////////////////////////////////////////////////////////////////////////////////////
 
 
    FILE * filewrite = fopen ( "30_5_06out.txt" , "w" );
 
    fprintf( filewrite, "%f ", result_center.x );
    fprintf( filewrite, "%f ", result_center.y );
    fprintf( filewrite, "%f", result_radius);
        fprintf( filewrite, "\n" );
 
        for ( i = 0; i < number_ofCover; i ++ )
        {
            fprintf( filewrite, "%f ", setOfPoints.cov_arr[i].x );
            fprintf( filewrite, "%f ", setOfPoints.cov_arr[i].y );
            fprintf( filewrite, "\n" );
        }
 
    fclose( filewrite );
 
return 0;
}
Добавлено через 17 часов 55 минут
Оболочку (Покрытие) Находит отлично! Проблема в проверки радиуса! он проверяет какие-то странные числа(( что в свою очередь связанно с нахождением центра описанной окружности(( ПОэтому помогите с центром!!!((

Добавлено через 5 часов 36 минут
Все я сделал!! ошибка в if ( sqrtemp_radius > radius ) return -666; нужно sqrtemp_radius - radius > 0.000000001
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
16.12.2012, 19:25
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Найти координаты центра и радиус минимального круга, который содержит все данные точки (C (СИ)):

Нарисовать графики нескольких окружностей разными цветами, зная координаты центра и радиус - C (СИ)
Мне нужно нарисовать графики нескольких окружностей разными цветами, зная координаты центра и радиус. В какой среде это лучше и проще...

Найти радиус окружности и площадь круга, ограниченного этой окружностью - C (СИ)
Дана длина L окружности. Найти ее радиус R и площадь S круга, ограниченного этой окружностью. В качестве значения π использовать 3.14.

Найти координаты низкой точки траектории и другой высшей точки подъема - C (СИ)
Заданные координаты точки подвески математического маятника A (x0, y0, z0) и координаты одной из точек его наивысшего положения B (x1, y1,...

Найти координаты самой низкой точки и другой нависшей точки подъема - C (СИ)
Помогите пожалуйста решить задачу. Только начал проходить программирование, и не знаю как написать код к данному заданию: Заданы точки...

Дана длина L окружности. Найти ее радиус R и площадь S круга, ограниченного этой окружностью. В качестве значения π использовать 3.14 - C (СИ)
Дана длина L окружности. Найти ее радиус R и площадь S круга, ограниченного этой окружностью. В качестве значения π использовать...

Найти точки пересечения параболы и круга - C (СИ)
Задали на паре задание: задаётся круг с координатами центра и радиуса, также задаётся квадратическая парабола. Нужно найти точки...

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
16.12.2012, 19:25
Привет! Вот еще темы с ответами:

Структуры: найти координаты центра окружности, пересекающейся с максимальным числом других окружностей - C (СИ)
Доброго времени суток! Прошу помочь мне с лабой. Вот задание: Задан массив из 6 данных типа структур. Структура включает: координаты...

Даны координаты центра круга и его радиус, а также координаты точки. Лежит ли эта точка внутри круга? - Delphi
Даны координаты центра круга и его радиус, а также координаты точки. Лежит ли эта точка внутри круга?

Определить минимальный радиус круга с центром в начале координат, который содержит все точки - Turbo Pascal
В одномерных массивах Х и Y одинакового размера n хранятся координаты n точек плоскости. Определить минимальный радиус круга с центром в...

Определить минимальный радиус круга с центром в начале координат, который содержит все точки - C++
1. В одномерном массиве с четным количеством элементов (2N) находятся координаты N точек плоскости. Они располагаются в следующем порядке:...


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

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

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