|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
25.11.2012, 16:40 | #1 |
Новичок
Джуниор
Регистрация: 25.11.2012
Сообщений: 1
|
Максимальное количество точек лежащих на одной прямой
Вводится множество точек на плоскости (с помощью координат этих точек). Построить список,
каждый элемент которого содержит координаты соответствующей точки. Удалить из списка минимальное количество элементов, так чтобы оставшиеся точки лежали на одной прямой. В построении списка и удалении элементов из него проблем нет. Не могу разобраться как найти прямую на которой лежит максимальное количество точек из заданных. Помогите пожалуйста |
25.11.2012, 16:53 | #2 |
Старожил
Регистрация: 09.01.2008
Сообщений: 26,229
|
последовательно, берёте пару точек, запоминаете её, строите уравнение прямой, проверяете сколько точек попадают на данную прямую.
Запоминаете это число. Повторяете в цикле, если число точек, попавших на прямую больше, чем запомненное, стираете предыдущее, запоминаете новую пару и количество точек. Выполняете цикл, пока не переберёте все пары. в результате получаете прямую, на которой лежит максимальное число точек. Удаляете все точки, которые не лежат на данной прямой. профит. p.s. можно оптимизировать быстродействие, если запоминать все точки, попавшие на прямую, для них уже перебор и проверку делать не надо, это позволит сократить количество перебираемых пар. Но, можно с этим и не заморачиваться! |
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Нахождение точек пересечения 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 |