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

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

Вернуться   Форум программистов > C/C++ программирование > Общие вопросы C/C++
Регистрация

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

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

Ответ
 
Опции темы Поиск в этой теме
Старый 25.11.2012, 16:40   #1
ccherya
Новичок
Джуниор
 
Регистрация: 25.11.2012
Сообщений: 1
Стрелка Максимальное количество точек лежащих на одной прямой

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


В построении списка и удалении элементов из него проблем нет. Не могу разобраться как найти прямую на которой лежит максимальное количество точек из заданных. Помогите пожалуйста
ccherya вне форума Ответить с цитированием
Старый 25.11.2012, 16:53   #2
Serge_Bliznykov
Старожил
 
Регистрация: 09.01.2008
Сообщений: 26,238
По умолчанию

последовательно, берёте пару точек, запоминаете её, строите уравнение прямой, проверяете сколько точек попадают на данную прямую.
Запоминаете это число.
Повторяете в цикле, если число точек, попавших на прямую больше, чем запомненное, стираете предыдущее, запоминаете новую пару и количество точек.
Выполняете цикл, пока не переберёте все пары.

в результате получаете прямую, на которой лежит максимальное число точек.
Удаляете все точки, которые не лежат на данной прямой.

профит.

p.s. можно оптимизировать быстродействие, если запоминать все точки, попавшие на прямую, для них уже перебор и проверку делать не надо,
это позволит сократить количество перебираемых пар. Но, можно с этим и не заморачиваться!
Serge_Bliznykov вне форума Ответить с цитированием
Ответ


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

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

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


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Нахождение точек пересечения n-угольника c прямой(c\c++)). forever042 Помощь студентам 5 17.12.2011 02:57
Задаnm n точек. Найти m=3,4... точек и построить на них m-угольник: количество точек , лежащих внутри и вне его мин. различается L.Rain Помощь студентам 0 11.12.2011 22:19
в массиве найти количество злементов лежащих в диапазоне от A до B Deniska112 Общие вопросы C/C++ 14 02.06.2009 17:59
вычислить количество элементов массива, лежащих в диапазоне от А до В Gigatrest Паскаль, Turbo Pascal, PascalABC.NET 16 26.01.2009 14:05