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

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

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 42, средняя оценка - 4.74
Protected_fleur
0 / 0 / 0
Регистрация: 29.06.2011
Сообщений: 77
29.06.2011, 15:22     Написать программу, определяющую радиус и центр окружности, проходящей по крайней мере через три различные точки заданного множества точек #1
Надо написать программу на СИ, определяюшую радиус и центр окружности, проходящей по крайней мере через три различные точки заданного множества точек на плоскости и содержащей внутри наибольшее количество точек этого множества. Помогите пожалуйста!
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.06.2011, 15:22     Написать программу, определяющую радиус и центр окружности, проходящей по крайней мере через три различные точки заданного множества точек
Посмотрите здесь:

C++ Из заданного на плоскости множества точек выбрать три различные точки
Найдите центр и радиус окружности, проходящей через три заданные точки на плоскости. C++
C++ Найти минимальный радиус шара, который будет охватывать все заданные точки(центр окружности лежит на одной из заданных точек)
Работа С Массивами (Выбрать три различные точки из заданного множества точек на плоскости так...) C++
C++ Определить радиус и центр окружности минимального радиуса, проходящей хотя бы через три различные точки заданного множества точек на плоскости
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Protected_fleur
0 / 0 / 0
Регистрация: 29.06.2011
Сообщений: 77
02.07.2011, 22:42  [ТС]     Написать программу, определяющую радиус и центр окружности, проходящей по крайней мере через три различные точки заданного множества точек #41
возможно, и я, когда стану опытным программистом, буду стонать, когда увижу свои отступы...

Добавлено через 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
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
02.07.2011, 22:44     Написать программу, определяющую радиус и центр окружности, проходящей по крайней мере через три различные точки заданного множества точек #42
Да, что-то не так. Переменная t обнуляется только вначале, а дальше только растёт. А ведь она считает точки внутри каждой окружности.
Protected_fleur
0 / 0 / 0
Регистрация: 29.06.2011
Сообщений: 77
03.07.2011, 13:31  [ТС]     Написать программу, определяющую радиус и центр окружности, проходящей по крайней мере через три различные точки заданного множества точек #43
вроде с подсчетом точек внутри разобралась...
А вот как теперь сделать, чтоб выбиралась окружность с наибольшим количеством точек внутри???
Помогите пожалуйста!
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
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
03.07.2011, 13:34     Написать программу, определяющую радиус и центр окружности, проходящей по крайней мере через три различные точки заданного множества точек #44
Вот там, где t1=t можно сохранять в отдельных переменных и окружность, и точки, по которым она построена.
После циклов вывести.
Protected_fleur
0 / 0 / 0
Регистрация: 29.06.2011
Сообщений: 77
03.07.2011, 14:00  [ТС]     Написать программу, определяющую радиус и центр окружности, проходящей по крайней мере через три различные точки заданного множества точек #45
Цитата Сообщение от grizlik78 Посмотреть сообщение
Вот там, где t1=t можно сохранять в отдельных переменных и окружность, и точки, по которым она построена.
После циклов вывести.
блин((( как это сделать???
нужно будет еще один цикл для того, чтоб наибольшее количество точек внутри находил?
grizlik78
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
03.07.2011, 14:03     Написать программу, определяющую радиус и центр окружности, проходящей по крайней мере через три различные точки заданного множества точек #46
Нет, зачем? Есть же уже поиск максимума:
C
1
2
3
4
if (t>t1)
{
    t1=t;
}
Действие внутри условия работает каждый раз, когда мы находим очередной максимум количества точек. Вот здесь и надо запомнить текущую окружность (и, возможно, точки, по которым она получена).
Protected_fleur
0 / 0 / 0
Регистрация: 29.06.2011
Сообщений: 77
03.07.2011, 14:08  [ТС]     Написать программу, определяющую радиус и центр окружности, проходящей по крайней мере через три различные точки заданного множества точек #47
Я не совсем представляю, как записать, чтоб он запоминал эту окружность...
нужно ввести новые переменные и присвоить им значение этой окружности...
вот и не знаю, а как им присвоить значение этой окружности...
grizlik78
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
03.07.2011, 14:19     Написать программу, определяющую радиус и центр окружности, проходящей по крайней мере через три различные точки заданного множества точек #48
C
1
2
3
4
5
6
7
8
9
circle big_circle;
/* ... */
/* тут всякие циклы и прочая */
/* ... */
if (t>t1)
{
    t1=t;
    big_circle = c;
}
Protected_fleur
0 / 0 / 0
Регистрация: 29.06.2011
Сообщений: 77
03.07.2011, 15:12  [ТС]     Написать программу, определяющую радиус и центр окружности, проходящей по крайней мере через три различные точки заданного множества точек #49
попробую разобраться...

Добавлено через 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
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
03.07.2011, 15:18     Написать программу, определяющую радиус и центр окружности, проходящей по крайней мере через три различные точки заданного множества точек #50
Насколько близко? Вообще, погрешность сравнения возможна, но она будет очень небольшой.
Protected_fleur
0 / 0 / 0
Регистрация: 29.06.2011
Сообщений: 77
03.07.2011, 15:36  [ТС]     Написать программу, определяющую радиус и центр окружности, проходящей по крайней мере через три различные точки заданного множества точек #51
ну где-то 0,5 см...может чуть меньше...
но если точки далеко ставить, то вроде норм все...
grizlik78
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
03.07.2011, 15:44     Написать программу, определяющую радиус и центр окружности, проходящей по крайней мере через три различные точки заданного множества точек #52
Цитата Сообщение от Protected_fleur Посмотреть сообщение
ну где-то 0,5 см...может чуть меньше...
но если точки далеко ставить, то вроде норм все...
Короче, меня интересуют точки, по которым построена окружность, сама окружность и точка, которая ошибочно относится внутрь.
Конкретные числа.
Protected_fleur
0 / 0 / 0
Регистрация: 29.06.2011
Сообщений: 77
03.07.2011, 16:01  [ТС]     Написать программу, определяющую радиус и центр окружности, проходящей по крайней мере через три различные точки заданного множества точек #53
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
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
03.07.2011, 16:24     Написать программу, определяющую радиус и центр окружности, проходящей по крайней мере через три различные точки заданного множества точек #54
Ну, вычисления проводятся с погрешностью, полностью от неё не избавиться всё-равно. Я бы наоборот, точки на окружности относил к внутренним, а для надёжности ещё и небольшую эпсилон вокруг добавил, то есть
(x-x0)^2+(y-y0)^2 <= R^2 + eps
Protected_fleur
0 / 0 / 0
Регистрация: 29.06.2011
Сообщений: 77
03.07.2011, 16:56  [ТС]     Написать программу, определяющую радиус и центр окружности, проходящей по крайней мере через три различные точки заданного множества точек #55
Спасибо большое за помощь
lemegeton
 Аватар для lemegeton
2910 / 1339 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
03.07.2011, 21:45     Написать программу, определяющую радиус и центр окружности, проходящей по крайней мере через три различные точки заданного множества точек #56
Если еще актуально.
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;
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.07.2011, 21:50     Написать программу, определяющую радиус и центр окружности, проходящей по крайней мере через три различные точки заданного множества точек
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
Protected_fleur
0 / 0 / 0
Регистрация: 29.06.2011
Сообщений: 77
03.07.2011, 21:50  [ТС]     Написать программу, определяющую радиус и центр окружности, проходящей по крайней мере через три различные точки заданного множества точек #57
спасибо, альтернативные решения всегда актуальны!
Yandex
Объявления
03.07.2011, 21:50     Написать программу, определяющую радиус и центр окружности, проходящей по крайней мере через три различные точки заданного множества точек
Ответ Создать тему

Метки
описанная окружность
Опции темы

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