Написать программу, определяющую радиус и центр окружности, проходящей по крайней мере через три различные точки заданного множества точек

@Protected_fleur · Регистрация: 29.06.2011

Студворк — интернет-сервис помощи студентам

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

@Protected_fleur · 02.07.2011, 22:42 **[ТС]**

возможно, и я, когда стану опытным программистом, буду стонать

, когда увижу свои отступы...

Добавлено через 53 минуты
Как всегда на чем-нибудь да спотыкаюсь...

Как мне сделать так, чтоб находилась окружность с наибольшим количеством точек внутри???
Я вот тут сделала, чтоб просто считал точки внутри... и то по-моему что-то не так...

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
int main() {
        int i, j, n, k, m, t=0, t1=0;
        circle c;
        
        printf("Enter number points( n>2 ): ");
        scanf("%d", &n);
        if(n<=2) { 
        printf("Number points is little");  
        _getch();
        return 0;  }
 
        float ** Points = new  float* [n];
        for (i=0; i<n; i++)
        {
                Points[i]= new float [2];
                printf("Enter pair[%d]:\n x: ", i + 1); 
                scanf("%f", &Points[i][0]);
                printf("y: ");              
                scanf("%f", &Points[i][1]); }
                
        for (i=0; i<n-2; i++)
        for (j=i+1; j<n-1; j++)
        for (k=j+1; k<n; k++)  {
            c = cir(
              Points[i][0], Points[i][1],
              Points[j][0], Points[j][1],
              Points[k][0], Points[k][1] ); 
              //проверка точек
        for (m=0; m<n; m++) {
        if ((Points[m][0]-c.x)*(Points[m][0]-c.x) + (Points[m][1]-c.y)*(Points[m][1]-c.y) <= c.r*c.r) t++;
        }
        if (t>t1)
        {
                  t1=t;
                  }  }
              
    printf("Center: (%g, %g)\n", c.x, c.y);
    printf("Radius: %g\n", c.r);
    printf("points inside: %d",t1);
        
        _getch();
        return 0;  }

помогите пожалуйста...

@grizlik78 · 02.07.2011, 22:44

Да, что-то не так. Переменная t обнуляется только вначале, а дальше только растёт. А ведь она считает точки внутри каждой окружности.

@Protected_fleur · 03.07.2011, 13:31 **[ТС]**

вроде с подсчетом точек внутри разобралась...
А вот как теперь сделать, чтоб выбиралась окружность с наибольшим количеством точек внутри???
Помогите пожалуйста!

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
int main() {
        int i, j, n, k, m, t1=0,t;
        circle c;
        
        printf("Enter number points( n>2 ): ");
        scanf("%d", &n);
        if(n<=2) { 
        printf("Number points is little");  
        _getch();
        return 0;  }
 
        float ** Points = new  float* [n];
        for (i=0; i<n; i++)
        {
                Points[i]= new float [2];
                printf("Enter pair[%d]:\n x: ", i + 1); 
                scanf("%f", &Points[i][0]);
                printf("y: ");              
                scanf("%f", &Points[i][1]); }
                
        for (i=0; i<n-2; i++)
        for (j=i+1; j<n-1; j++)
        for (k=j+1; k<n; k++)  {
            c = cir(
              Points[i][0], Points[i][1],
              Points[j][0], Points[j][1],
              Points[k][0], Points[k][1] ); 
             //проверка точек
        t=0;
        for (m=0; m<n; m++) 
        {
        if ((Points[m][0]-c.x)*(Points[m][0]-c.x) + (Points[m][1]-c.y)*(Points[m][1]-c.y) <= c.r*c.r) t++;
        }
        if (t>t1)
        {
                  t1=t;
                  }  }
    printf("Center: (%g, %g)\n", c.x, c.y);
    printf("Radius: %g\n", c.r);
    printf("points inside: %d",t1);
        
        _getch();
        return 0;  }

@grizlik78 · 03.07.2011, 13:34

Вот там, где t1=t можно сохранять в отдельных переменных и окружность, и точки, по которым она построена.
После циклов вывести.

@Protected_fleur · 03.07.2011, 14:00 **[ТС]**

Сообщение от grizlik78

Вот там, где t1=t можно сохранять в отдельных переменных и окружность, и точки, по которым она построена.
После циклов вывести.

блин((( как это сделать???
нужно будет еще один цикл для того, чтоб наибольшее количество точек внутри находил?

@grizlik78 · 03.07.2011, 14:03

Нет, зачем? Есть же уже поиск максимума:

C
1
2
3
4
if (t>t1)
{
    t1=t;
}

Действие внутри условия работает каждый раз, когда мы находим очередной максимум количества точек. Вот здесь и надо запомнить текущую окружность (и, возможно, точки, по которым она получена).

@Protected_fleur · 03.07.2011, 14:08 **[ТС]**

Я не совсем представляю, как записать, чтоб он запоминал эту окружность...
нужно ввести новые переменные и присвоить им значение этой окружности...
вот и не знаю, а как им присвоить значение этой окружности...

@grizlik78 · 03.07.2011, 14:19

C
1
2
3
4
5
6
7
8
9
circle big_circle;
/* ... */
/* тут всякие циклы и прочая */
/* ... */
if (t>t1)
{
    t1=t;
    big_circle = c;
}

@Protected_fleur · 03.07.2011, 15:12 **[ТС]**

попробую разобраться...

Добавлено через 50 минут

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
int main() {
        int i, j, n, k, m, t1=0,t;
        circle c;
        circle big_circle;
        
        printf("Enter number points( n>2 ): ");
        scanf("%d", &n);
        if(n<=2) { 
        printf("Number points is little");  
        _getch();
        return 0;  }
 
        float ** Points = new  float* [n];
        for (i=0; i<n; i++)
        {
                Points[i]= new float [2];
                printf("Enter pair[%d]:\n x: ", i + 1); 
                scanf("%f", &Points[i][0]);
                printf("y: ");              
                scanf("%f", &Points[i][1]); }
                
        for (i=0; i<n-2; i++)
        for (j=i+1; j<n-1; j++)
        for (k=j+1; k<n; k++)  {
            c = cir(
              Points[i][0], Points[i][1],
              Points[j][0], Points[j][1],
              Points[k][0], Points[k][1] ); 
             //проверка точек
        t=0;
        for (m=0; m<n; m++) 
        {
        if ((Points[m][0]-c.x)*(Points[m][0]-c.x) + (Points[m][1]-c.y)*(Points[m][1]-c.y) < c.r*c.r) t++;
        }
        if (t>t1)
        {
                  t1=t;
    big_circle = c;
    printf("Center: (%g, %g)\n", big_circle.x, big_circle.y);
    printf("Radius: %g\n", big_circle.r);
    printf("points inside: %d\n\n",t1);
                  }
          }
        
        _getch();
        return 0;  }

и снова проблема возникла

точка находится снаружи,но близко к окружности, а ее считает как будто она внутри...потому что похоже значение радиуса в квадрате получается больше...
подскажите пожалуйста, что мне сделать

@grizlik78 · 03.07.2011, 15:18

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

@Protected_fleur · 03.07.2011, 15:36 **[ТС]**

ну где-то 0,5 см...может чуть меньше...
но если точки далеко ставить, то вроде норм все...

@grizlik78 · 03.07.2011, 15:44

Сообщение от Protected_fleur

ну где-то 0,5 см...может чуть меньше...
но если точки далеко ставить, то вроде норм все...

Короче, меня интересуют точки, по которым построена окружность, сама окружность и точка, которая ошибочно относится внутрь.
Конкретные числа.

@Protected_fleur · 03.07.2011, 16:01 **[ТС]**

Enter number points( n>2 ): 9
Enter pair[1]:
x: 0
y: 4
Enter pair[2]:
x: 1.5
y: 1.5
Enter pair[3]:
x: 2
y: 2
Enter pair[4]:
x: 4
y: 4
Enter pair[5]:
x: 5
y: 2
Enter pair[6]:
x: 7
y: 1
Enter pair[7]:
x: 8
y: 7
Enter pair[8]:
x: 10
y: 4
Enter pair[9]:
x: 11
y: 8
Center: (0.75, 2.75)
Radius: 1.45774
points inside: 3

Center: (2, 3.5)
Radius: 2.06155
points inside: 4

Center: (2.92105, 4.05263)
Radius: 2.92153
points inside: 5

Center: (4.59615, 5.05769)
Radius: 4.71628
points inside: 6

Center: (5, 5.3)
Radius: 5.16624
points inside: 8

Center: (59.5, -142.5)
Radius: 158.122
points inside: 9

Ну здесь проблема только в том, что он находит точки, которые внутри окружности и на ней...
а так как я указала, что
(x-x0)^2+(y-y0)^2 < R ^2
то, точки которые лежат на окружности не должны подсчитываться...

@grizlik78 · 03.07.2011, 16:24

Ну, вычисления проводятся с погрешностью, полностью от неё не избавиться всё-равно. Я бы наоборот, точки на окружности относил к внутренним, а для надёжности ещё и небольшую эпсилон вокруг добавил, то есть
(x-x0)^2+(y-y0)^2 <= R^2 + eps

@Protected_fleur · 03.07.2011, 16:56 **[ТС]**

Спасибо большое за помощь

@lemegeton · 03.07.2011, 21:45

Если еще актуально.

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
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
#define epsilon 0.0001
 
typedef struct {
  float x;
  float y;
} Point;
 
typedef struct {
  Point center;
  float radius;
} Circle;
 
int Compare(float a, float b) {
  return (fabs(a - b) < epsilon) ? 0 :
    ((a > b) ? 1 : -1);
}
 
float Distance(Point *a, Point *b) {
  return sqrt(pow(a->x - b->x, 2.) + pow(a->y - b->y, 2.));
}
 
Circle GetCircle(Point *a, Point *b, Point *c) {
  Circle result;
  result.center.x = result.center.y = result.radius = 0;
  if (Compare(b->x, a->x) == 0 || Compare(c->x, b->x) == 0)
    return result;
  float angle_a = (b->y - a->y) / (b->x - a->x);
  float angle_b = (c->y - b->y) / (c->x - b->x);
  if (Compare(angle_a, angle_b) == 0 || Compare(angle_a, 0.) == 0 ||
    Compare(angle_a, 0.) == 0)
    return result;
  result.center.x = (angle_a * angle_b * (a->y - c->y) + angle_b * (a->x + b->x) +
    angle_a * (b->x + c->x)) / (2. * (angle_b - angle_a));
  result.center.y = (-1. / angle_a) * (result.center.x - (a->x + b->x) / 2.) +
    (a->y + b->y) / 2.;
  result.radius = Distance(&result.center, a);
  return result;
}
 
int IsEmptySicrle(Circle *circle) {
  return (Compare(circle->center.x, 0.) == 0 &&
    Compare(circle->center.y, 0.) == 0 &&
    Compare(circle->radius, 0.) == 0);
}
 
int AllPointsInCircle(Circle *circle, Point *points, size_t number_of_points) {
  int i;
  if (IsEmptySicrle(circle)) return 0;
  for (i = 0; i < number_of_points; ++i)
    if (Compare(circle->radius, Distance(&circle->center, &points[i])) == -1)
      return 0;
  return 1;
}
 
int main(int argc, char *argv[]) {
  srand(time(NULL));
  const size_t number_of_points = 15;
  Point *points = (Point*)malloc(sizeof(Point) * number_of_points);
  int i, j, k;
 
  for (i = 0; i < number_of_points; ++i) {
    points[i].x = rand() % 1000 / 100.;
    points[i].y = rand() % 1000 / 100.;
    printf("(%.2f, %.2f) ", points[i].x, points[i].y);
  }
  printf("\n");
 
  for (i = 0; i < number_of_points - 2; ++i)
    for (j = i + 1; j < number_of_points - 1; ++j)
      for (k = j + 1; k < number_of_points; ++k) {
        Circle circle = GetCircle(&points[i], &points[j], &points[k]);
        if (AllPointsInCircle(&circle, points, number_of_points))
          printf("Found: (%.2f, %.2f) radius %.2f\n", circle.center.x,
            circle.center.y, circle.radius);
      }
  return 0;
}

@Protected_fleur · 03.07.2011, 21:50 **[ТС]**

спасибо, альтернативные решения всегда актуальны!

@Ivan_probofall · 31.05.2018, 18:12

А как сделать,чтобы считались точки не внутри?

@Anastasia_1906 · 20.12.2020, 09:34

Сообщение от grizlik78

F12

можно ли пожалуйста ка-нибудь исправить эту ошибку? так как мне нужно именно на языке С++, хоть С и может работать как С++, но это не то, подскажи пожалуйста, что туда нужно поставить вместо F12 или как это исправить? Заранее большие спасибки тебе

@grizlik78 · 20.12.2020, 11:40

<F12> вставил мой редактор при случайном нажатии на эту клавишу. Надо просто удалить, т.е. вместо

C++
1
circle circumscr<F12>ibed(

должно было быть

C++
1
circle circumscribed(

Новые блоги и статьи Все статьи Все блоги /
Родители токсичные абьюзеры по отношению к своим детям ругают их оскорбляют не любят zorxor 08.11.2026 Жить в атмосфере постоянных оскорблений, критики и холодности со стороны родителей — это тяжелое и болезненное испытание, которое оставляет глубокие эмоциональные раны. Токсичное и абьюзивное. . .	Как только я захожу к себе в свою комнату я сразу же с себя снимаю свои трусы. Ответ от Джемени ИИ. zorxor 08.11.2026 Джемени, как только я захожу к себе в свою комнату я сразу же с себя снимаю свои трусы. Многие люди, возвращаясь домой, сразу переодеваются в максимально свободную одежду или вовсе предпочитают. . .	Паттерн очереди действий/команд (Action / Command Queue). Система очереди действий и кат-сцен с SDL3 Callbacks, cglm и OpenGL 8Observer8 07.11.2026 Содержание блога \| English Version Руководство для начинающих по реализации паттерна очереди действий/ команд (Action / Command Queue) на C++ (C++20) с использованием официального SDL3 Callbacks. . .	Проверка полного ФИО в типовом справочнике Maks 07.11.2026 Решение реализовано в конфигурации КА2, на примере справочника "КонтактныеЛицаПартнеров". Задача: Запрет инициалов. Не допускаеть использование сокращений вида "И. И. ", "И. И. ", "И И" и. . .
Про "Windows must die!" kumehtar 04.11.2026 Знаете, чет накатило. . . . Когда-то это было почти боевым кличем: мол, нормальный человек сидит на DOS, OS/ 2 или Linux, а вот это вот - Must Die. А теперь человек произносит «мастдай» с усмешкой - и. . .	Красочные поля с номером страницы svg+background-image russiannick 04.11.2026 Красочные поля с номером страницы не менее важны чем в эпоху бумажных книг. Посему спешу представить почтеннейшей публике этот важный инструмент который эти поля и формирует. В процессе разработки. . .	Вступаем в новую фазу генерации favicons, векторную. russiannick 02.11.2026 Теперь нет нужды скрывать что используется простой svg. Исходный код изображения помещаем в поле и жмем кнопку. Исходник преобразуется в вид корректный для помещения в favicon или в url(). Нажатие. . .	Генератор паролей (вариант №4) Maks 01.11.2026 После публикации 3-го варианта генератора паролей, разослал его своим коллегам (с целью оценки), в итоге были получены следующие рекомендации: 1. Вернуть возможность использования знаков \| 1 l I;. . .

@Protected_fleur 0 / 0 / 1 Регистрация: 29.06.2011 Сообщений: 77

	Написать программу, определяющую радиус и центр окружности, проходящей по крайней мере через три различные точки заданного множества точек 29.06.2011, 15:22. Показов 18947. Ответов 60 Метки описанная окружность (Все метки) Надо написать программу на СИ, определяюшую радиус и центр окружности, проходящей по крайней мере через три различные точки заданного множества точек на плоскости и содержащей внутри наибольшее количество точек этого множества. Помогите пожалуйста! 0

@grizlik78 2383 / 1667 / 279 Регистрация: 29.05.2011 Сообщений: 3,402
	02.07.2011, 22:44
	Да, что-то не так. Переменная t обнуляется только вначале, а дальше только растёт. А ведь она считает точки внутри каждой окружности. 0

@grizlik78 2383 / 1667 / 279 Регистрация: 29.05.2011 Сообщений: 3,402
	03.07.2011, 13:34
	Вот там, где t1=t можно сохранять в отдельных переменных и окружность, и точки, по которым она построена. После циклов вывести. 0

@Protected_fleur 0 / 0 / 1 Регистрация: 29.06.2011 Сообщений: 77
	03.07.2011, 14:08 [ТС]
	Я не совсем представляю, как записать, чтоб он запоминал эту окружность... нужно ввести новые переменные и присвоить им значение этой окружности... вот и не знаю, а как им присвоить значение этой окружности... 0

@grizlik78 2383 / 1667 / 279 Регистрация: 29.05.2011 Сообщений: 3,402
	03.07.2011, 15:18
	Насколько близко? Вообще, погрешность сравнения возможна, но она будет очень небольшой. 0

@Protected_fleur 0 / 0 / 1 Регистрация: 29.06.2011 Сообщений: 77
	03.07.2011, 15:36 [ТС]
	ну где-то 0,5 см...может чуть меньше... но если точки далеко ставить, то вроде норм все... 0

@Protected_fleur 0 / 0 / 1 Регистрация: 29.06.2011 Сообщений: 77
	03.07.2011, 16:01 [ТС]
	Enter number points( n>2 ): 9 Enter pair[1]: x: 0 y: 4 Enter pair[2]: x: 1.5 y: 1.5 Enter pair[3]: x: 2 y: 2 Enter pair[4]: x: 4 y: 4 Enter pair[5]: x: 5 y: 2 Enter pair[6]: x: 7 y: 1 Enter pair[7]: x: 8 y: 7 Enter pair[8]: x: 10 y: 4 Enter pair[9]: x: 11 y: 8 Center: (0.75, 2.75) Radius: 1.45774 points inside: 3 Center: (2, 3.5) Radius: 2.06155 points inside: 4 Center: (2.92105, 4.05263) Radius: 2.92153 points inside: 5 Center: (4.59615, 5.05769) Radius: 4.71628 points inside: 6 Center: (5, 5.3) Radius: 5.16624 points inside: 8 Center: (59.5, -142.5) Radius: 158.122 points inside: 9 Ну здесь проблема только в том, что он находит точки, которые внутри окружности и на ней... а так как я указала, что (x-x0)^2+(y-y0)^2 < R ^2 то, точки которые лежат на окружности не должны подсчитываться... 0

@grizlik78 2383 / 1667 / 279 Регистрация: 29.05.2011 Сообщений: 3,402
	03.07.2011, 16:24
	Ну, вычисления проводятся с погрешностью, полностью от неё не избавиться всё-равно. Я бы наоборот, точки на окружности относил к внутренним, а для надёжности ещё и небольшую эпсилон вокруг добавил, то есть (x-x0)^2+(y-y0)^2 <= R^2 + eps 0

@Protected_fleur 0 / 0 / 1 Регистрация: 29.06.2011 Сообщений: 77
	03.07.2011, 16:56 [ТС]
	Спасибо большое за помощь 0

@Protected_fleur 0 / 0 / 1 Регистрация: 29.06.2011 Сообщений: 77
	03.07.2011, 21:50 [ТС]
	спасибо, альтернативные решения всегда актуальны! 0

@Ivan_probofall 0 / 0 / 0 Регистрация: 01.04.2017 Сообщений: 4
	31.05.2018, 18:12
	А как сделать,чтобы считались точки не внутри? 0