Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Передача вектора по ссылке https://www.cyberforum.ru/ cpp-beginners/ thread1667730.html
Как передать в функцию вектор по ссылке/указателю, чтобы не происходило его постоянное копирование?
Выбрать 4 числа с минимальной разницей между максимальным и минимальным числом из 4 векторов разной длины C++
Здравствуйте, у меня такая задача: Даны 4 вектора размера от 1 до 100 000 В каждый записываются числа от 1 до 100 000 Надо найти такую 4-ку ( по 1 числу из каждого вектора) , чтобы разница между...
C++ Хеш таблицы с раздельным связыванием
Необходимо реализовать класс для работы с хеш таблицами с раздельным связыванием. Что такое хеш функции немного имею представление, а вот что такое раздельное связывание, нет. Попробовал...
C++ Структура содержит название книги, автора, год издания. Удалить издания с годом меньше заданного Структура содержит название книги, автора, год издания. Удалить издания с годом меньше заданного. https://www.cyberforum.ru/ cpp-beginners/ thread1667682.html
C++ Как оформить ввод с клавиатуры названий? https://www.cyberforum.ru/ cpp-beginners/ thread1667674.html
Есть задача Где я должен сравнить дни недели, если это дни от понедельника - четверг (1-4), то вывожу одно, если это 5 день, вывожу другое, если 6, то третье, если 7, то четвертое. Вот код ...
C++ Не получается считать значение параметров из командной строки
Нужно cоставить программу , которая выводит на экран значение функции F(x) в заданном диапазоне .Диапазон и шаг изменения аргумента пользователь задает в командной строке ; в том случае , если в...
Найти наименьший общий делитель в произвольном массиве C++
Товарищи, доброго времени суток! Никак не могу совладать с алгоритмистикой данной задачи - вроде результат при некоторых значениях выдаётся корректный, но не всегда. Задача такая: Найти...
C++ Вывод на экран количества нулевых элементов одномерного динамического массива и их порядковых номеров Помогите решить задачу! Разработать метод для вывода на экран количества нулевых элементов одномерного динамического массива и их порядковых номеров! https://www.cyberforum.ru/ cpp-beginners/ thread1667637.html
C++ Найти значения выражений по заданным математическим формулам https://www.cyberforum.ru/ cpp-beginners/ thread1667633.html
Составить программу для расчета заданных выражений. Вводить исходные данные с клавиатуры. Обязательно проверять исключительные ситуации. Значение \pi= 3,1415926. t=\frac{2\cos \left(x-\frac{\pi...
C++ Программа с функцией, вычисляющей площадь поверхности цилиндра Кому не сложно, помогите с программой. Нужно создать программу с функцией, вычисляющей площадь поверхности цилиндра (создайте прототип и определение этой функции) https://www.cyberforum.ru/ cpp-beginners/ thread1667621.html
1 / 1 / 0
Регистрация: 25.05.2013
Сообщений: 29
21.02.2016, 17:27 0

Найти прямую, котороя проходит не менее чем через четыре точки из заданного множества

21.02.2016, 17:27. Просмотров 445. Ответов 4
Метки (Все метки)

Ответ


Последовательно (либо рандомно) перебирать всевозможные пары вершин. Для каждой пары составляем уравнение прямой Ax+By+C=0, где A=y1-y2; B=x2-x1; C=x1y2-x2y1.
Для остальных точек проверяем принадлежность построенной прямой. То есть если в уравнении прямой при подстановке координат точки выполняется тождество, то точка принадлежит прямой, иначе нет.
Как только нашли 2 такие точки (еще по 2ум построена прямая 2+2=4), то завершаем работу.
Если прошли все точки и не нашли нужной прямой, то ее не существует.

Это алгоритм "в лоб", и сложность у него при самой грубой оценке O(n^3). Наверняка можно как-то улучшить.

Вернуться к обсуждению:
Найти прямую, котороя проходит не менее чем через четыре точки из заданного множества
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
21.02.2016, 17:27
Готовые ответы и решения:

Найти проекции каждой точки заданного множества в пространстве на заданную прямую
Найти проекции каждой точки заданного множества в трёхмер- ном пространстве на заданную прямую.

Найти прямую (в пространстве), которая проходит через точку и две прямые
Найти прямую, которая проходит через точку P(0,3,-2) и прямые {L}_{1}\ :\...

Найти проекцию точки М(1,1,1) на прямую проходящую через точки М1(2,5,-3) и М2 (3,-2,2).
Найти проекцию точки М(1,1,1) на прямую проходящую через точки М1(2,5,-3) и М2 (3,-2,2).

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

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