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

Найти паралелограмм с наибольшим количеством точек - C++

Восстановить пароль Регистрация
 
Alleshka
0 / 0 / 0
Регистрация: 24.12.2012
Сообщений: 7
24.12.2012, 09:59     Найти паралелограмм с наибольшим количеством точек #1
Приветствую всех. Обращаюсь с помощью, так как эта программа уже выводит меня из себя. Задание состоит в следующем:

"Даны N точек на плоскости. Найти среди них точки являющиеся вершинами фигуры, содержащей максимальное число заданных точек. Фигура - параллелограм."

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

Пытался проделать следующее:

Отсортировав все точки, которые идут из двух входных файлов, перебираю все точки. Кстати, с сортировкой тоже есть проблемы. Дальше, проверяю прямые на парную параллельность и, если они паралельны, то проверяю другие прямые. Если 4 прямые попарно паралельны, это параллелограм, проверял через угол наклона. Но уже на этом этапе столкнулся с проблемой, если прямая перпендикулярна Ох, то, по формуле, происходит деление на ноль.


После того, как находим паралелограм хотел перевести все 4 прямые в уравнение прямой, а дальше проверить неравенством.


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


Формулы:

k - Коэффициент наклона
k=(Y2-Y1)/(X2-X1);
b=(X2*Y1-Y2*X1)/(X2-X1);

Уравнение прямой:
y=k*x+b;
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
24.12.2012, 09:59     Найти паралелограмм с наибольшим количеством точек
Посмотрите здесь:

Найти в тексте все слова с наибольшим количеством гласных букв русского алфавита C++
C++ в интервале от a до b найти число с наибольшим количеством делителей
C++ Имеется 15 строк, найти строку с наибольшим количеством слов палиндромов
C++ Найти слово с наибольшим количеством гласных букв
C++ Вывод содержимого вектора с наибольшим количеством строк
C++ Найти слова с наибольшим количеством гласных букв
C++ Определить строку с наибольшим количеством отрицательных элементов
Найти в двумерном массиве строку с наибольшим количеством одинаковых элементов C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Alleshka
0 / 0 / 0
Регистрация: 24.12.2012
Сообщений: 7
28.01.2013, 05:56  [ТС]     Найти паралелограмм с наибольшим количеством точек #2
Тему можно закрывать. Вот он быдлокод.
Yandex
Объявления
28.01.2013, 05:56     Найти паралелограмм с наибольшим количеством точек
Ответ Создать тему
Опции темы

Текущее время: 23:23. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru