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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Насютка
0 / 0 / 0
Регистрация: 27.02.2014
Сообщений: 36
#1

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

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

Определить радиус и центр окружности, проходящей, по крайней мере, через три
различные точки заданного множества точек на плоскости и, содержащей внутри наибольшее
количество точек этого множества
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
06.03.2014, 15:46
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Написать программу, определяющую радиус и центр окружности, проходящей по крайней мере через три различные точки заданного множества точек (C++):

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

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

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

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

Из заданного на плоскости множества точек выбрать три различные точки - C++
Здравствуйте, помогите пожалуйста написать программу: Из заданного на плоскости множества точек выбрать три различные точки так, чтобы...

Из заданного на плоскости множества точек выбрать три различные точки - C++
Само задание звучит так: "Из заданного на плоскости множества точек выбрать три различные точки так, чтобы разность между площадью...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
gunslinger
случайный прохожий
1133 / 751 / 191
Регистрация: 20.07.2013
Сообщений: 2,071
06.03.2014, 22:13 #2
http://algolist.manual.ru/maths/geom...ion/circle.php
http://ru.wikipedia.org/wiki/%D0%9E%...81%D1%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 Кб, 11 просмотров)
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.03.2014, 22:13
Привет! Вот еще темы с ответами:

Работа С Массивами (Выбрать три различные точки из заданного множества точек на плоскости так...) - C++
Задание: Выбрать три различные точки из заданного множества точек на плоскости так, чтобы была минимальной разность между количествами...

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

Найти минимальный радиус шара, который будет охватывать все заданные точки(центр окружности лежит на одной из заданных точек) - C++
есть программа, проблема в передаче массива в функцию a #include &quot;stdio.h&quot; #include &quot;conio.h&quot; #include &quot;math.h&quot; #include...

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


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

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

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