Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 03.07.2012, 10:14   #1
Day Stiff
 
Регистрация: 14.12.2011
Сообщений: 6
По умолчанию Геометрическая задача - Нахождение числа отрезков (С++)

Задача:
На плоскости задано множество точек, каждая пара из которых определяет отрезок. Найти отрезок, который пересекается с максимальным числом остальных отрезков.

нужно ещё это как то вывести в графической форме.
плюс есть код похожей геометрической задачи, которую написал сам преподаватель.
Day Stiff вне форума Ответить с цитированием
Старый 03.07.2012, 11:06   #2
DiemonStar
Старожил
 
Регистрация: 08.02.2012
Сообщений: 2,173
По умолчанию

А. Делаете пребор всех возможных отрезков:
1. цикл первой точки (i от 1 до n -1)
2. цикл для второй точки (j от i+1 до n)

Б. для каждого из отрезков выбираете второй отрезок для проверки пересечения аналогичным циклом (не забывайте проверять на совпадение с исходным отрезком)
В. проверяете пересечение отрезков (хоть через уравнения прямых линий и проверку попадания в отрезки)
Правильно поставленная задача - три четверти решения.
DiemonStar вне форума Ответить с цитированием
Старый 04.07.2012, 11:32   #3
Day Stiff
 
Регистрация: 14.12.2011
Сообщений: 6
По умолчанию

а алгоритм перебора не подскажешь? нигде не нашёл
Day Stiff вне форума Ответить с цитированием
Старый 04.07.2012, 11:33   #4
Day Stiff
 
Регистрация: 14.12.2011
Сообщений: 6
По умолчанию

хотя отыскал Бентли — Оттмана, но так и не разобрался как это на с++ изобразить
Day Stiff вне форума Ответить с цитированием
Старый 04.07.2012, 11:42   #5
DiemonStar
Старожил
 
Регистрация: 08.02.2012
Сообщений: 2,173
По умолчанию

Цитата:
а алгоритм перебора не подскажешь? нигде не нашёл
на Паскале выглядит так:
Код:
var Points : array (1...N) of TPoint;
....
For I := 1 to N-1 do
  For J := I + 1 to N do
     begin {перебор всех возможных отрезков без повторов} end;
Правильно поставленная задача - три четверти решения.
DiemonStar вне форума Ответить с цитированием
Старый 10.07.2012, 10:14   #6
Day Stiff
 
Регистрация: 14.12.2011
Сообщений: 6
По умолчанию

как для каждого выбрать другой второй для проверки?
Day Stiff вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

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

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
геометрическая задача Nurik1 Паскаль, Turbo Pascal, PascalABC.NET 1 05.12.2011 11:34
геометрическая задача Nurik1 Паскаль, Turbo Pascal, PascalABC.NET 3 20.11.2011 12:07
Геометрическая задача Liza Dalbek Помощь студентам 2 22.12.2010 19:48