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

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Подгонка решения задачи под тесты Timus Online Judge, С++ http://www.cyberforum.ru/cpp-beginners/thread1112761.html
На Timus Online Judge столкнулся с довольно простой задачей, с которой у меня возникли некоторые проблемы. Задача: Программист Денис c детства мечтал побывать в Антарктиде, но почему-то регулярных рейсов туда нет. Поэтому Денис все лето изучал Антарктиду с помощью соседнего кинотеатра. Теперь он знает, что в Антарктиде водится несколько видов пингвинов: Императорские пингвины (Emperor...
C++ Списки языка C++ Удаление нужного элемента Все не могу реализовать удаление нужного мне элемента из писка памогите написать функцию удаления введенного элемента. #include<iostream> #include<fstream> #include<string> #include<conio.h> using namespace std; struct link http://www.cyberforum.ru/cpp-beginners/thread1112742.html
Рекурсия. Вывести на экран все перестановки чисел от 1 до n в лексикографическом порядке. C++
При помощи рекурсии по данному числу n выведите на экран все перестановки чисел от 1 до n в лексикографическом порядке. Нужен текст программы, пример выполнения, блок схема.
Область видимости и указатели C++
Разбираю пример Иногда возникают ситуации, когда значение локальной переменной за пределами блока, в котором она объявлена. Как быть в этом случае? Здесь нам и пригодятся указатели. int main() { int test; int test_loop;
C++ Разработайте перегруженные функции нахождения среднего арифметического и среднего геометрического трех целых и вещественных чисел http://www.cyberforum.ru/cpp-beginners/thread1112720.html
Составьте программу для решения задачи. Выясните, что больше: среднее арифметическое или среднее геометрическое трех положительных чисел. Разработайте перегруженные функции нахождения среднего арифметического и среднего геометрического трех целых и вещественных чисел. Желательно пример выполнения программы и блок-схему.
C++ Написать программу, подсчитывающую количества слов в текстовом файле Написать программу, подсчитывающую количества слов в текстовом файле. Нужно использовать File-New-Aplication + добавить кнопки и т д. Народ помогите пожалуйста, мучаюсь 2ой день, так и не понял как сделать. P.C. Хотелось бы сразу получить rar архив, т.к. как там эти кнопки делать я тоже не совсем пойму. Спасибо большое. подробнее

Показать сообщение отдельно
gunslinger
случайный прохожий
1132 / 750 / 191
Регистрация: 20.07.2013
Сообщений: 2,067
06.03.2014, 22:13     Написать программу, определяющую радиус и центр окружности, проходящей по крайней мере через три различные точки заданного множества точек
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 Кб, 10 просмотров)
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru