Форум программистов, компьютерный форум, киберфорум
Наши страницы

Дано несколько точек с целочисленными координатами. Определить максимальное количество точек из них, лежащих на одной прямой. Если можно напечатать н - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Не могу понять чего не работает http://www.cyberforum.ru/cpp-beginners/thread589762.html
Не могу понять чего не работает моя (функция sort) сортировка мозги уже кипят, а надо всего лишь сделать сортировку по алфавиту но не выходит помогите а? выводы я так делал... что б видно самому...
C++ List Control win api Добрый день. Помогите с зозданием list control. Создал в visual c++ 6.0 шаблон "Hello world". Добавил в диалоговое окно about list control. Не могу добавить в него строку. Как это сделать?LRESULT... http://www.cyberforum.ru/cpp-beginners/thread589757.html
Изображение мигающей лампочки C++
Такая задачка для С++ : Написать программу С++ при запуске которой на экране появляется изображение мигающей лампочки. Помогите пожалуйста.
C++ Определить количество строк, содержащих хотя бы один нулевой элемент
Дана целочисленная прямоугольная матрица. Определить: 1) количество строк, содержащих хотя бы один нулевой элемент; 2) номер столбца, в котором находится самая длинная серия одинаковых...
C++ Даны вещественные матрица Х(15,20) и мас¬сив Y(15). Заменить четные столбцы матрицы на вектор Y http://www.cyberforum.ru/cpp-beginners/thread589731.html
Даны вещественные матрица Х(15,20) и мас¬сив Y(15). Заменить четные столбцы матрицы на вектор Y.
C++ Вывести первое слово начинающееся на гласную букву Разработать программу: 1. Выводящую список слов во введенном предложении; 2. Выводящую первое слово, начинающееся с гласной буквы во введенном предложении. unsigned char M; char x,y; ... подробнее

Показать сообщение отдельно
Paporotnik
383 / 227 / 7
Регистрация: 06.07.2011
Сообщений: 512
29.05.2012, 00:51
за эффективность не отвечаю. но ничего эффективнее O(2*n*n) в худшем случае (если у нас больше двух точек на одной прямой нигде не лежит) в голову не лезет.

алгоритм на псевдокоде:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
maxCollinearPoints = 0;      //собственно максимальное число точек на одной прямой
foreach (points as currentPoint) {     //перебираем все точки
   coefficientsFrequencyList             //инициализируем частотный словарь для коэффициентов
   currentCCSOrigin = currentPoint    //назначаем новый центр координат
   foreach (points as otherPoint) {    //для всех точек (на самом деле "для оставшихся", но это не важно)
       tempOtherPoint = otherPoint-currentCCSOrigin       //пересчитываем координаты в новой системе, вычитая x1-x0 и y1-y0
       pointCoefficient = tempOtherPoint.x / tempOtherPoint.y    //считаем коэффициент
       coefficientsFrequencyList.insert(pointCoefficient)      //заносим коэффициент в частотный словарь
   }
   maxCollinearPointsInCurrentCCS = 0      //в каждой новой системе координат максимальное число коллинеарных точек новое
   foreach (coefficientsFrequencyList as currentCoefficient) {    //находим самый часто встречающийся коэффициент и получаем максимальное число точек на одной прямой
       if (currentCoefficient.count > maxCollinearPointsInCurrentCCS) {
           maxCollinearPointsInCurrentCCS = currentCoefficient.count
       }
   }
   if (maxCollinearPointsInCurrentCCS > maxCollinearPoints) {     //если полученное число точек для данной системы координат больше полученных до этого для других, то оно новое максимальное
       maxCollinearPoints = maxCollinearPointsInCurrentCCS
   }
}
//в итоге в maxCollinearPoints ответ
суть в том, что если точки лежат на одной прямой с центрмо координат, то их коэффициент k будет одинаков. поочередно переносим центр координат в каждую точку, считаем коэффициенты и частоту их повторений. частота наиболее популярного коэффициента и будет максимальным числом точек на одной прямой. самая большая частота для всех систем координат и есть ответ.

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