Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 19.03.2010, 17:39
Новичок

Отправить личное сообщение для Basil2009 Посмотреть профиль Найти все сообщения от Basil2009
 
Регистрация: 19.03.2010
Сообщений: 7

Алгоритм-программа "Бомба"
Требуется составить алгоритм—программу для определения наименьшей окружности (центр и минимальный радиус), охватывающей не менее K из N заданных точек на плоскости.
Исходные точки на плоскости (х1 у1), (х2,у2),..., (хN, уN) задаются в текстовом файле. Результаты расчетов (координаты центра окружности, радиус ее и точки (xi,уi, попадающие в окружность) сохранить в текстовом файле. Решите эту же задачу, но искомая окружность должна включать все заданные точки (хi,уi). Подскажите пожалуйста алгоритм! Буду очень благодарен!

Последний раз редактировалось Basil2009, 19.03.2010 в 18:04.
  #2  
Старый 19.03.2010, 18:31
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

алгоритм для окружности, покрывающей все точки
http://www.inf.ethz.ch/personal/gaertner/miniball.html
  #3  
Старый 20.03.2010, 11:01
Новичок

Отправить личное сообщение для Basil2009 Посмотреть профиль Найти все сообщения от Basil2009
 
Регистрация: 19.03.2010
Сообщений: 7

Спасибо вам добрый человек)) Вот я только совсем чайник)) Это программа в консоли или для MFC написано . да и еще, минимальный нужен радиус в этом то вся и проблема, окружность которая очерчивает все точки в принципе не сложно сделать)ХД, а вот чтобы минимальную и при этом охватывала все точки, это непросто, с преподом сидели думали так и ничего не придумали))ХД. Да и еще в чем разница между Miniball.h и Miniball_dynamic_d.h?
  #4  
Старый 20.03.2010, 12:39
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

>в чем разница между Miniball.h и Miniball_dynamic_d.h?
там написано - размерность пространства передается как аргумент конструктора и может быть задана во время выполнения (это актуально для случаев точек в трехмерном и т.д. пространстве)

>а вот чтобы минимальную и при этом охватывала все точки, это непросто,

Алгоритм как раз и находит окружность минимального радиуса, охватывающую все точки.

Еще можно поискать книгу Berg Overmars computational geometry, там тоже есть smallest enclosing disc (minidisc)
  #5  
Старый 20.03.2010, 14:44
Новичок

Отправить личное сообщение для Basil2009 Посмотреть профиль Найти все сообщения от Basil2009
 
Регистрация: 19.03.2010
Сообщений: 7

Правильно ли я понял ссылку на сайт который вы дали там полностью листинг программы, копипасть и все)))ХД))) эмм..поможет разобраться что где там))) как читать данные из файла и записывать вроде знаю))?? Спасибо вам еще раз.
  #6  
Старый 21.03.2010, 11:17
Местный

Отправить личное сообщение для prografix Посмотреть профиль Найти все сообщения от prografix
 
Регистрация: 03.11.2006
Адрес: Москва
Сообщений: 167

Можешь посмотреть мою программу нахождения минимальной окружности, но там без ввода-вывода. Это уже делай сам. Или с преподом.
  #7  
Старый 08.04.2010, 15:45
Новичок

Отправить личное сообщение для Basil2009 Посмотреть профиль Найти все сообщения от Basil2009
 
Регистрация: 19.03.2010
Сообщений: 7

Сообщение от prografix Посмотреть сообщение
Можешь посмотреть мою программу нахождения минимальной окружности, но там без ввода-вывода. Это уже делай сам. Или с преподом.
Код:
#include "math.h"

#include "rand.h"
#include "func2d.h"
#include "Vector2d.h"
#include "Vector3d.h"
#include "ShevArray.h"
#include "WireModel.h"
#include "Mathem.h"
#include "opti2d.h"

typedef unsigned int nat;

//**************************** 23.08.2003 *********************************//
//
//          Минимальная охватывающая окружность
//
//**************************** 04.11.2009 *********************************//

Circle2d minCircle ( CArrRef<Vector2d> points )
{
    nat n = points.size();
    if ( n == 0 ) return Circle2d ();
    if ( n == 1 ) return Circle2d ( 0, points[0] );
    if ( n == 2 )
    {
        const Vector2d o = 0.5 * ( points[0] + points[1] );
        return Circle2d ( norm2 ( points[0] - o ), o );
    }
    const Vector2d ** p = new const Vector2d *[n];
    nat i;
    for ( i = 0; i < n; ++i ) p[i] = & points[i];
    PRand rand;
    for ( i = 0; i < n; ++i )
    {
        nat j = rand.number(n);
        if ( i != j )
        {
            const Vector2d * t = p[i];
            p[i] = p[j];
            p[j] = t;
        }
    }
    Vector2d o = 0.5 * ( *p[0] + *p[1] );
    double q = qmod ( *p[0] - o );
    for ( nat i1 = 2; i1 < n; ++i1 )
    {
        const Vector2d & v1 = *p[i1];
        if ( qmod ( v1 - o ) <= q ) continue;
        o = 0.5 * ( v1 + *p[0] );
        q = qmod ( v1 - o );
        for ( nat i2 = 1; i2 < i1; ++i2 )
        {
            const Vector2d & v2 = *p[i2];
            if ( qmod ( v2 - o ) <= q ) continue;
            o = 0.5 * ( v1 + v2 );
            q = qmod ( v1 - o );
            for ( nat i3 = 0; i3 < i2; ++i3 )
            {
                const Vector2d & v3 = *p[i3];
                if ( qmod ( v3 - o ) <= q ) continue;
                circlePPP ( v1, v2, v3, o, q );
            }
        }
    }
    delete[] p;
    return Circle2d ( sqrt ( q ), o );
О господи помогите разобраться))
  #8  
Старый 08.04.2010, 21:36
Местный

Отправить личное сообщение для prografix Посмотреть профиль Найти все сообщения от prografix
 
Регистрация: 03.11.2006
Адрес: Москва
Сообщений: 167

Если что-то непонятно - спрашивай. А так, конечно, тут много моих классов.
  #9  
Старый 09.04.2010, 03:44
Новичок

Отправить личное сообщение для Basil2009 Посмотреть профиль Найти все сообщения от Basil2009
 
Регистрация: 19.03.2010
Сообщений: 7

эм...где здесь объявление переменных) И на выходе что выдает алгорит уже отрисованный круг?
Цитата:
#include "rand.h"
#include "func2d.h"
#include "Vector2d.h"
#include "Vector3d.h"
#include "ShevArray.h"
#include "WireModel.h"
#include "Mathem.h"
#include "opti2d.h"
здесь много не стандатрных библиотек, я вот только не знаю как не свои библиотеки подключать?) да и еще, в принципе мне не нужна отрисовка), координаты центра окружности, радиус ее и точки (xi,уi, попадающие в окружность,) записанные в файл, как это из твоиго алгоритма вытащить, грубо говоря, за помощь скину рублей 200)
  #10  
Старый 09.04.2010, 11:46
Местный

Отправить личное сообщение для prografix Посмотреть профиль Найти все сообщения от prografix
 
Регистрация: 03.11.2006
Адрес: Москва
Сообщений: 167

Можешь прочитать описание этого алгоритма по ссылке. Там есть одна неточность о которой я написал в комментарии.
Что касается моей программы, то лучше обсуждать её не здесь, а по почте.
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Алгоритм Грэхема и алгоритм "заворачивания подарка" habibibi Реализация, исходники, языки 1 02.02.2010 19:57
Построение пирамиды из "Х" и " " с помощью for. Alexander_ua Задачи 3 10.11.2009 13:35
[язык Си] Задача "Скрудж МакДак",поиск в глубину гость Графы 0 18.03.2009 03:21
Проверка на существование/отсутствие предыдущего поколение в игре "Жизнь" гость Сортировка и поиск 0 02.12.2007 00:31
просьба создать раздел форума с названием "графы" CD_Eater Замечания о работе сайта 1 22.09.2006 10:56