Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
1 / 1 / 2
Регистрация: 18.11.2013
Сообщений: 337
1

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

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

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

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

Найти прямую (в пространстве), которая проходит через точку и две прямые
Найти прямую, которая проходит через точку 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
542 / 485 / 104
Регистрация: 05.05.2014
Сообщений: 1,110
21.02.2016, 17:22 2
ilya0610, Увы! Это не всегда возможно!
0
1 / 1 / 0
Регистрация: 25.05.2013
Сообщений: 29
21.02.2016, 17:27 3
Последовательно (либо рандомно) перебирать всевозможные пары вершин. Для каждой пары составляем уравнение прямой Ax+By+C=0, где A=y1-y2; B=x2-x1; C=x1y2-x2y1.
Для остальных точек проверяем принадлежность построенной прямой. То есть если в уравнении прямой при подстановке координат точки выполняется тождество, то точка принадлежит прямой, иначе нет.
Как только нашли 2 такие точки (еще по 2ум построена прямая 2+2=4), то завершаем работу.
Если прошли все точки и не нашли нужной прямой, то ее не существует.

Это алгоритм "в лоб", и сложность у него при самой грубой оценке O(n^3). Наверняка можно как-то улучшить.
0
125 / 117 / 67
Регистрация: 07.11.2014
Сообщений: 788
21.02.2016, 17:31 4
Можно найти все точки, у которых y или x равны друг другу.. Если будет 4 таких точек - задача выполнена... Однако по диагонали тоже могут быть прямые..
0
Эксперт С++
3206 / 1733 / 435
Регистрация: 03.05.2010
Сообщений: 3,867
21.02.2016, 18:06 5
Цитата Сообщение от ilya0610 Посмотреть сообщение
подскажите, алгоритм выполнения вот такого задания. Есть какое-то количество точек. Необходимо найти прямую через которую проходит не менее 4 точек.
Если представить точки комплексными числами, то можно так. Находим разности всех точек со всеми кроме себя. Оставляем из этих разностей только те, у которых аргумент (угол с осью x) от 0 до 180 градусов. Для n точек таких разностей будет n*(n - 1)/2. Затем сортируем их по аргументу. Если чисел с каким-то аргументом будет шесть или больше - среди этих точек искать кандидатов.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
21.02.2016, 18:06

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Выбрать четыре различные точки первого множества по правилу
Пытаюсь написать программу но не доходит как это сделать: Даны два множества точек на плоскости....

Среди заданного множества точек найти две точки с максимальным расстоянием между ними
Среди заданного множества точек найти две точки с максимальным расстоянием между ними. то есть...

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
5
Ответ Создать тему
Опции темы

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