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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Alleshka
0 / 0 / 0
Регистрация: 24.12.2012
Сообщений: 7
#1

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

24.12.2012, 09:59. Просмотров 311. Ответов 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++ Найти столбец матрицы с наибольшим количеством нулей
C++ В интервале от a до b найти число с наибольшим количеством делителей
C++ Имеется 15 строк, найти строку с наибольшим количеством слов палиндромов
C++ Найти слово с наибольшим количеством гласных букв
C++ Вывод содержимого вектора с наибольшим количеством строк
C++ Найти слова с наибольшим количеством гласных букв
Найти в двумерном массиве строку с наибольшим количеством одинаковых элементов 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     Найти паралелограмм с наибольшим количеством точек
Ответ Создать тему
Опции темы

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