Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.92/13: Рейтинг темы: голосов - 13, средняя оценка - 4.92
0 / 0 / 0
Регистрация: 27.02.2014
Сообщений: 36
1

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

06.03.2014, 15:46. Просмотров 2569. Ответов 1
Метки нет (Все метки)


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

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

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

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

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

__________________
Помогаю в написании студенческих работ здесь.
Записывайтесь на профессиональные курсы C++ разработчиков
1
случайный прохожий
1502 / 999 / 372
Регистрация: 20.07.2013
Сообщений: 2,895
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);
}
//---------------------------------------------------------------------------
0
Миниатюры
Написать программу, определяющую радиус и центр окружности, проходящей по крайней мере через три различные точки заданного множества точек  
Вложения
Тип файла: zip circle.zip (60.2 Кб, 25 просмотров)
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
06.03.2014, 22:13

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь или здесь.

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

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

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

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


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

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

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