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

Поиск точек на плоскости - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Перенос строк по символу http://www.cyberforum.ru/cpp-beginners/thread799465.html
Нужно написать программу, которая ищет в введенном тексте все символы '?', удаляет их и ставит после каждого из них перенос строки Удаление символов реализовал в одну строку, но с переносом что-то пошло не так) Вот код функции, подскажите, пожалуйста, как это сделать? Предполагаю, что через инсерт, но как-то не выходит AnsiString s = Memo_in->Text; while(s.Pos("?")) {...
C++ Координаты точек на выпуклой оболочке Привет всем. Помогите пожалуйста с задачей :) В общем, есть множество точек на плоскости, и надо найти точки (и, соответственно, их координаты), которые будут находиться на выпуклой оболочке. http://www.cyberforum.ru/cpp-beginners/thread799455.html
C++ Соотношение Безу, как работает программа
Добрый день! Прошу вашей помощи! Объясните мне, как работает программа %-) int main() { int a, b, p=1, q=0, r=0, s=1, k, x, y; cin >> a >> b;
Динамический массив. Подсчитать, сколько различных видов товаров было привезено на состав этого дня C++
Недавно начал учить массивы и не могу до конца разобраться с динамическими массивами. Нужно реализовать задачу, в которой неизвестно заранее количество элементов массива. Можно ли ее как-то реализовать с помощью new? Условие задачи: "Диспетчер заносила в базу данных номера товаров, которые поступали на склад в течение дня. Подсчитать, сколько различных видов товаров было привезено на состав...
C++ Разработка многопользовательского графического чата http://www.cyberforum.ru/cpp-beginners/thread799445.html
Разработка многопользовательского графического чата Общение: при помощи прямолинейных линий, создаваемых курсором мыши. Особенность: добавить авторизацию пользователей. Данные передавать в закодированном виде. Алгоритм кодирования: Роторная машина.
C++ Как созать цикл for для нахождения произведения элементов массива Вот к примеру для нахождения суммы необходимо так: for (i=0, sum=0; i<n; i++ ) sum+=m; А вот как для нахождения произведения у меня что-то не получается! подробнее

Показать сообщение отдельно
tur9
43 / 4 / 1
Регистрация: 20.08.2012
Сообщений: 89
04.03.2013, 20:57     Поиск точек на плоскости
У меня похожая задача. (но не про классы, программирование, а про алгоритм)
Есть N точек на плоскости.
Надо найти все группы точек, находящиеся друг от друга на расстоянии R или меньше.
Как это сделать оптимально?
Допустим так:
Создаем массив bol в N членов для отметки использованных точек и заполняем его нулями.

1. Берем первую точку (из массива точек) и ищем среди оставшихся точек те, которые по Х не отличаются более чем на +/- R. Находим например К точек.
2. Среди этих К точек ищем те, которые по Y не отличаются более чем на +/- R от первой точки. Допустим нашли Р таких точек.
3. Среди Р точек ищем те, которые внутри радиуса R от первой точки. Допустим нашли М таких точек.

После нахождения этих М точек имеем также их индексы из исходного массива N точек. В соответствующих индексах помечаем в массиве bol что эти точки уже использованы (ставим туда напр 1) и не подлежат дальнейшим вычислениям.

Ищем следующую свободную точку в массиве N при учете, что на соответствующем месте в bol есть ноль.
Повторяем процесс с учетом того что не следует брать точки для которых в bol уже 1

На сколько оптимален по времени этот алгоритм? Может есть лучший?
 
Текущее время: 04:03. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru