0 / 0 / 0
Регистрация: 27.02.2014
Сообщений: 36
1

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

06.03.2014, 15:46. Показов 3751. Ответов 3
Метки нет (Все метки)

Определить радиус и центр окружности, проходящей, по крайней мере, через три
различные точки заданного множества точек на плоскости и, содержащей внутри наибольшее
количество точек этого множества
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
06.03.2014, 15:46
Ответы с готовыми решениями:

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

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

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

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

3
случайный прохожий
2088 / 1354 / 465
Регистрация: 20.07.2013
Сообщений: 3,790
06.03.2014, 22:13 2
Лучший ответ Сообщение было отмечено Насютка как решение

Решение

http://algolist.manual.ru/math... circle.php
http://ru.wikipedia.org/wiki/%... 1%82%D1%8C
Задача показалась интересной и нетривиальной.
Код ниже далек от совершенства, не проверяется деление на ноль, когда нельзя построить окружность для данных трех точек (см. конец статьи по первой ссылке), но такая ситуация достаточно редка.
Вызвала сложность проверка на возможность построения окружности, содержащей в себе все точки (возможно ли это в любом случае, не знаю). Я использовал тройки точек, максимально близких к разным углам формы (таких различных случаев всего 4, выбирается тот, для которого попадание точек в окружность происходит наилучшим образом). Наверняка существует гораздо более оптимальный алгоритм.
Точки генерируются случайным образом и распределяются в центральной четверти формы. Изменением переменной p (по умолчанию =750) можно увеличить область, но принципиальной разницы нет.
При генерации точек замена
random(p/2)+p/4 на random(p)
позволит распределить точки (теоретически) по все форме.
Количество точек определяет параметр n (=25).

Builder:
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
//---------------------------------------------------------------------------
 
#include <vcl.h>
#pragma hdrstop
 
#include "Unit1.h"
//---------------------------------------------------------------------------
#pragma package(smart_init)
#pragma resource "*.dfm"
TForm1 *Form1;
//---------------------------------------------------------------------------
__fastcall TForm1::TForm1(TComponent* Owner)
    : TForm(Owner)
{
}
//---------------------------------------------------------------------------
double koef(TPoint a, TPoint b)
{
  return (b.y-a.y)*1./(b.x-a.x);
}
//---------------------------------------------------------------------------
int centerX(double koefa, double koefb, TPoint a, TPoint b, TPoint c)  // koefa == koef21, koefb == koef32
{
  return (koefa*koefb*(a.y-c.y)+koefb*(a.x+b.x)-koefa*(b.x+c.x))/2/(koefb-koefa);
}
//---------------------------------------------------------------------------
int centerY(double koefa, int x, TPoint a, TPoint b)
{
  return -(x-(a.x+b.x)/2.)/koefa+(a.y+b.y)/2.;
}
//---------------------------------------------------------------------------
int radius(TPoint a, TPoint b)
{
  return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
//---------------------------------------------------------------------------
struct CR
{
  TPoint center;
  int radius, count;
}id;
//---------------------------------------------------------------------------
const n = 25, p = 750;
TPoint z[n];
CR InnerDots(int exclude_corner)
{
  CR cr;
  TPoint temp[3], corner[3], center;
  switch (exclude_corner)
  {
    case 0:
      corner[0] = TPoint(p, 0);
      corner[1] = TPoint(0, p);
      corner[2] = TPoint(p, p);
      break;
    case 1:
      corner[0] = TPoint(0, 0);
      corner[1] = TPoint(0, p);
      corner[2] = TPoint(p, p);
      break;
    case 2:
      corner[0] = TPoint(0, 0);
      corner[1] = TPoint(p, 0);
      corner[2] = TPoint(p, p);
      break;
    case 3:
      corner[0] = TPoint(0, 0);
      corner[1] = TPoint(p, 0);
      corner[2] = TPoint(0, p);
  }
/*  corner[0] = TPoint(0, 0);
  corner[1] = TPoint(p, 0);
  corner[2] = TPoint(0, p);
  corner[3] = TPoint(p, p);*/
  double k1, k2, angle;
  int r, i, j, count = 0;
 
  center.x = p/2;
  center.y = p/2;
  for (i = 0; i < 4; i++)
    temp[i] = center;
 
  for (i = 0; i < n; i++)
    for (j = 0; j < 3; j++)
      if (radius(z[i], corner[j]) > radius(temp[j], corner[j]))
        temp[j] = z[i];
 
  k1 = koef(temp[0], temp[1]);
  k2 = koef(temp[1], temp[2]);
  center.x = centerX(k1, k2, temp[0], temp[1], temp[2]);
  center.y = centerY(k1, center.x, temp[0], temp[1]);
  r = radius(center, temp[0]);
  cr.center = center;
  cr.radius = r;
 
  for (i = 0; i < n; i++)
    if (radius(z[i], center) <= r+1)  // r+1, а не r - чтобы сократить влияние округлений при подсчете точек
      count++;
  cr.count = count;
  return cr;
}
//---------------------------------------------------------------------------
void __fastcall TForm1::Button1Click(TObject *Sender)
{
  ClientHeight = p;
  ClientWidth = p;
  TPoint center;
  double angle;
  int r, i, count = 0;
  InvalidateRect(NULL, NULL, 1);
 
  randomize();
  for (i = 0; i < n; i++)
  {
    z[i].x = random(p/2)+p/4;
    z[i].y = random(p/2)+p/4;
    Canvas->Pixels[z[i].x][z[i].y] = clBlack;
  }
 
  for (i = 0; i < 4; i++)
  {
    id = InnerDots(i);
    if (id.count > count)
    {
      count = id.count;
      center = id.center;
      r = id.radius;
    }
    if (id.count == n)
      break;
  }
 
  for (i = 0; i < 100000; i++)
  {
    angle = 2*M_PI*i/p;
    Canvas->Pixels[r*cos(angle)+center.x][r*sin(angle)+center.y] = clRed;
  }
 
  Caption = "Окружность: радиус R = " + String(r) + ", центр - (" + String(center.x) + ", " + String(center.y) + "), точек внутри окружности - " + String(count);
}
//---------------------------------------------------------------------------
Миниатюры
Написать программу, определяющую радиус и центр окружности, проходящей по крайней мере через три различные точки заданного множества точек  
Вложения
Тип файла: zip circle.zip (60.2 Кб, 31 просмотров)
0
0 / 0 / 0
Регистрация: 16.05.2022
Сообщений: 2
17.05.2022, 17:01 3
gunslinger, можете помочь с задачей?
0
случайный прохожий
2088 / 1354 / 465
Регистрация: 20.07.2013
Сообщений: 3,790
17.05.2022, 19:49 4
С какой задачей? Чем помочь?

Добавлено через 5 минут
Если с этим: Выбрать максимальное подмножество попарно не связных друг с другом окружностей, то посмотри Круги, что образуют самую длинную цепь - выделить отдельным цветом, рисование на канве. Только там "наоборот", но, может, что-то нужное найдется.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
17.05.2022, 19:49
Помогаю со студенческими работами здесь

Определить радиус и центр окружности, проходящей по крайней мере через три различные точки
11. Определить радиус и центр окружности, проходящей по крайней мере через три различные точки...

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

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

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


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru