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

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

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

Как найти трапеции среди заданных точек на плоскости? - C++

08.12.2013, 01:37. Просмотров 454. Ответов 0
Метки нет (Все метки)

Задано N точек, среди них нужно найти все трапеции и вывести координаты той(тех), в которой содержится наибольшее кол-во заданных точек.
В вики трапеция определяется как четырехугольник, у которого только пара сторон параллельны. Следовательно, можно в цикле N раз брать точку, находить направляющие вектора(дальше просто "вектора") до каждой точки кроме ее самой(N-1), от той в свою очередь находить вектора до каждой точки кроме первых двух(N-2), то же самое с третьей(N-3), а от четвертой только найти вектор до первой. Так мы переберем все четырехугольники. Затем мы сравниваем вектора и если два равны, а два других нет, то фигура будет являться трапецией. Далее проверяем не было ли у нас трапеции с такими же координатами и, если нет, то находим кол-во входящих в нее точек(тоже хороший вопрос - думал найти площадь трапеции и сравнить ее с суммой площадей 4-х треугольников с вершинами: проверяемая точка и две рядом лежащие вершины трапеции. но, даже если не считать вершины трапеции входящими точками, нам нужно проверить N-4 точек, что не очень хорошо), записываем в файл координаты вершин трапеции и кол-во входящих точек, а также кол-во точек в какую-нибудь переменную Max, если прошлое значение меньше. Потом просто выводим Max и координаты трапеций содержащие Max точек. Вот, собственно, единственный алгоритм, который пришел в голову.
Вопрос: есть ли более простой способ решения этой задачи? Или какие-нибудь замечания по моему способу и будет ли он корректно работать?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.12.2013, 01:37     Как найти трапеции среди заданных точек на плоскости?
Посмотрите здесь:
C++ Среди заданных точек на плоскости найти ту, у которой расстояние суммы равно наибольшему от остальных точек
C++ Дано множество точек на плоскости, заданных полярными координатами. Получить декартовы координаты этих точек
C++ Найти среди прямых, заданных на плоскости, ту прямую, которая имеет наибольшее число пересечений с остальными
C++ Среди треугольников с вершинами в заданном множестве точек на плоскости
C++ В заданном множестве точек плоскости найти количество точек в каждой из четвертей
C++ В заданном множестве точек плоскости найти количество точек в каждой из четвертей
Из множества точек на плоскости найти точки, образующие параллелограмм с наибольшим количеством точек внутри C++
Функция, которая вернет номера двух из трех заданных точек на плоскости, расстояние между которыми минимально C++
Найти из двух точек на плоскости ближайшую к заданной точке C++
Найти количество отрицательных чисел среди заданных C++
C++ Среди заданных целых чисел k,l,m найти пары кратных
C++ Среди заданных треугольников найти треугольник максимальной площади

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

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