|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
|
Опции темы | Поиск в этой теме |
29.05.2012, 14:04 | #1 |
Регистрация: 28.05.2012
Сообщений: 5
|
множество точек на плоскости
задано множество точек на плоскости. перечислить все различные максимальные подмножества точек, лежащих на одной прямой, которые содержат более двух точек.
|
29.05.2012, 14:51 | #2 |
Старожил
Регистрация: 09.01.2008
Сообщений: 26,229
|
а что такое "максимальное подмножество" ?!
берете две точки, выводите для них уравнение прямой, проверяете, попадают ли ещё точки на эту прямую. считаете количество попавших точек. если это значение больше максимального значения (в начале присвоить ему ноль) - то обнулить все сохранённые комбинации и запомнить текущую комбинацию точек. если значение равно максмальному, проверить, была ли такая комбинация ранее, если нет - сохранить эту комбинацию. А конекретная реализация будет зависеть в первую очередь от числа точек и от того, как они представлены. Как и где накапливать найденные подмножества (если их вообще нужно накапливать - потому как можно первый раз пройтись в цикле, найти максимальное КОЛИЧЕСТВО точек, лежащих на одной прямой, потом ещё раз в цикле по всем парам точек пройтись - выдавая на экран те подмножества, где количество точек на одной прямой равно максимальному количеству, найденному при первом цикле перебора... |
29.05.2012, 15:00 | #3 |
Регистрация: 28.05.2012
Сообщений: 5
|
есть код похожий проги. как переделать под мою? очень надо
Код:
|
29.05.2012, 20:11 | #4 |
Форумчанин
Регистрация: 05.09.2011
Сообщений: 869
|
мне особенно нравится, когда вместо ответа на вопрос начинают пихать всякие затычки..
Серж, "максимальное", думаю, означает, что если есть 10 точек на одной прямой, то комбинации из 3, 4...8, 9 входящих в этот десяток точек перечислять не надо. P.S. Сергей15, не похоже, что "очень надо". Надо было бы - либо сделал бы, либо хоть на вопросы отвечал..
Предпочитаю на "ты".
|
30.05.2012, 01:08 | #5 | ||
Старожил
Регистрация: 09.01.2008
Сообщений: 26,229
|
Цитата:
А "различные максимальные подмножества" — это, вероятно, ВСЕ наборы точек, количеством более трёх, лежащие на одной прямой (т.е. хоть там три точки лежит на прямой, хоть 25 точек (на другой прямой) - все эти наборы должны быть выведены. самое сложное - это как отсечь те наборы, которые уже были ранее.. интуитивно чувствую, что для этого должно быть какое-то несложное условие проверки... (можно, конечно, банально сохранять пару точек, для который вывод набора уже был ранее, но тогда нужно организовывать динамическую структуру. да и не очень это красиво и эффективно... Ничего в голову не приходит - как отбрасывать отработанные варианты? Цитата:
|
||
30.05.2012, 21:10 | #6 | |
Старожил
Регистрация: 08.04.2012
Сообщений: 3,229
|
Цитата:
Мне кажется, оптимальное решение проблемы состоит в том, чтобы избавиться от этой проблемы в зародыше. В данном случае - не отсекать дубли, а не допускать их с самого начала. А для этого нужно на каждом этапе исключать из рассмотрентя точки. 1. Цикл по первой точке отрезка прямой. 2. Вложенный цикл по второй точке на отрезке - ее номер всегда больше, чем у первой (номера меньше первой исключаем). 3. Вложенный цикл по оставшимся точкам - окажутся ли они на прямой, проходящей через первые две точки. Номера всех этих точек больше номера второй (номера меньше второй исключаем). При таком порядке перебора формируемая последовательность точек всегда оказывается упорядоченной по номерам, т.е. исключает появление "перестановок". Ну и объем вычислений - по минимуму. Правда, сложность все равно O(n^3). Последний раз редактировалось s-andriano; 30.05.2012 в 21:16. |
|
31.05.2012, 04:55 | #7 | ||
Форумчанин
Регистрация: 05.09.2011
Сообщений: 869
|
Задачка меня зацепила )). Думал над ней несколько часов, благо как раз пришлось несколько длительных поездок на машине - прекрасное время для долбежки по задаче: руки не хватаются за клаву сразу )). Но все же сначала сделал вариант, от которого потом пришел в ужас и стер нафик. Запасайтесь кофе и терпением, господа..
Сначала отвечу на последний пост: Цитата:
Хотя в принципе я согласен - различные варианты надо пресекать на корню. Вопрос - как? Цитата:
Главное, что я вынес из неудачи с решением (примерно) по описаной выше схеме, можно выразить так: не надо определять принадлежность точки к прямой, проходящей через две выбранных. Основные положения решения таковы: 1. Определить понятие ЛИНИИ (прямой). То есть, сделать некую числовую структуру, по которой однозначно рисуется линия. 2. Сделать понятие линии однозначным. То есть, если две линии равны, то структуры, их определяющие, также должны быть равны. Предусмотреть функцию определения равенства линий. 3. Рассчитать матрицу линий. 4. Создать матрицу элементов типа boolean, отмечающую использованность каждого элемента матрицы линий (каждая линия используется только один раз - в отличие от каждой точки, которая может быть использована сколько угодно раз). 5. Во вложенном цикле по элементам матрицы линий накапливать множество номеров точек, относящихся к равным линиям. Если во внешнем цикле получается множество из более, чем двух точек - выводить его на печать. (Тут подразумевается, что всего точек не более 255) 6. Скомпилировать, запустить, отвесить челюсть, почесать репу и балдеть. (сообщение пришлось разбить на два, посколку я превысил длину 5000 символов, так что код будет приведен в следующем посте)
Предпочитаю на "ты".
|
||
31.05.2012, 04:58 | #8 |
Форумчанин
Регистрация: 05.09.2011
Сообщений: 869
|
(начало см. в предыдущем посте)
А вот и код: Код:
а. Для определения структуры линии я использовал нечто похожее на т.н. нормальное уравнение линии (см. wikipedia.ru). Для вычисления расстояния от точки до линии использовал формулу Герона-Архимеда, наклон прямой через банальный ArcTan. б. По ходу возник вопрос - а что делать, если точки совпадают? Сначала я хотел это как-то разумно решить (и таки решил, если у каждой точки не более одной копии), но потом подумал, что овчинка не стоит выделки, и бросил на полпути - то есть решил, что в условие следует добавить, что все точки различны. Вариант, корректно (вроде) работающий для указанного выше случая остался (могу привести).
Предпочитаю на "ты".
|
02.06.2012, 12:10 | #9 | |||||||
Старожил
Регистрация: 08.04.2012
Сообщений: 3,229
|
Цитата:
Т.е. нужен алгоритм, который как-то обрабатывает множество точек. Причем это множество для его алгоритмической обработки уже должно быть упорядоченным (неважно, как, собссно), поэтому такой порядок мы будем считать естественным и не будем его нарушать. Т.к. незачем. Под отрезком прямой я подразумеваю упорядоченное множество из двух точек, являющееся подмножеством исходного множества точек. При решении задачи перебираются все возможные отрезки. Для чего используется вложенный цикл, во внешнем - перебор по первой точке, во внутреннем - по второй. При этом номер второй точки в естественном порядка всегда больше номера первой. Так мы будем уверены, что каждый из отрезков рассматривается только один раз. Цитата:
Цитата:
Цитата:
Почему матрица? Из каких элементов она состоит? Я так понимаю, раз матрица, количество ее элементов O(n^2)? Цитата:
Цитата:
Цитата:
Из словесного описания алгоритм не понял. Будет время - посмотрю текст программы. По поводу точек с повторяющимися координатами: Мне кажется, тут можно устранить проблему предварительной обработкой массива точек - из него "выбрасываются" дубли, но при этом записывается кратность каждой точки. Сложность O(n*log(n)), пусть даже O(n^2). Итого, точку можно описать структурой: - координаты: 2D-вектор, - номер в исходной последовательности (именно его будем использовать при выводе результата): целое число, - кратность точки: целое число, - индекс следующей "выброшенной" точки - для организации списка: целое число. |
|||||||
02.06.2012, 19:54 | #10 | ||
Старожил
Регистрация: 08.04.2012
Сообщений: 3,229
|
Андрей, похоже, мы несколько по-разному понимаем условие задачи.
ТС пишет: Цитата:
Цитата:
Я оформил Ваш код в виде процедуры, для чего, правда, пришлось вынести массивы в глобальные переменные, т.к. иначе у меня стек переполнялся уже при количестве точек 123. В Вашем же решении выдаются ВСЕ множества точек при количестве последних больше 2, что видно уже при количестве точек равном 9. Смотрим дальше. При количестве точек равном 40 Ваш код не находит комбинации по 5 точек, а при 70 - по 6. Ну а вариант с 256 точками дает восзиожность оценить ресурсоемкость алгоритма по времени и памяти. Код:
|
||
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Даны координаты n точек на плоскости. Найти номера двух точек, расстояние между которыми наибольшее. | Viwwna | Паскаль, Turbo Pascal, PascalABC.NET | 2 | 19.11.2011 06:33 |
множество точек с++ | Hecpon | Помощь студентам | 6 | 21.12.2009 21:18 |
определить радиус и центр окружности, на кот. лежит наиб.число точек заданного на плоскости мн-ва точек) | kcю | Помощь студентам | 0 | 17.11.2009 19:50 |
множество точек))) | kcю | Помощь студентам | 0 | 11.11.2009 21:32 |