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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.78
lumpochka
0 / 0 / 0
Регистрация: 28.05.2012
Сообщений: 10
#1

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

28.05.2012, 23:41. Просмотров 1240. Ответов 4
Метки нет (Все метки)

Я подумала, что нужно будет написать класс Point. Немного написала, и остановилась на методе, который проверяет принадлежность точки прямой. И вообще, непонятно какой должен быть тип этой функции - bool, что ли? Помогите закончить программу, пожалуйста!!!
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
using namespace std;
// описание класса Point
class Point {
 int x, y; 
public:
 Point(int x0, int y0)
 {
 x = x0;
 y = y0;
 }
 void ShowPoint()
 {
 cout << "x = " << x;
 cout << "y = " << y;
 }
void main()
{}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
28.05.2012, 23:41     Дано несколько точек с целочисленными координатами. Определить максимальное количество точек из них, лежащих на одной прямой. Если можно напечатать н
Посмотрите здесь:
Определить количество точек, лежащих на заданной прямой C++
вычислите количество точек с целочисленными координатами,находящиеся в круге C++
C++ Найти все подмножества точек, лежащих на одной прямой
Найти количество точек с целочисленными координатами внутри заданного отрезка C++
C++ Количество точек с целочисленными координатами внутри (не включая границ) произвольного многоугольника
C++ Найти в бинарном файле все пары точек, лежащих с точкой d на одной прямой
Вычислить k-количество точек с целочисленными координатами, попадающих в круг ра-диуса R(R>0) с центром в начале координат C++
Вычислить количество точек с целочисленными координатами, попадающими в круг радиуса R>0 с центром в начале координат C++
Определить, сколько точек с целочисленными координатами попадают в круг заданного радиуса с центром в начале координат C++
C++ Дано множество точек на плоскости, заданных полярными координатами. Получить декартовы координаты этих точек
C++ Обработка массива точек заданных их целочисленными координатами
Определить взаимное расположение трех точек на плоскости (совпадают, на одной прямой, создают треугольник) C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Paporotnik
383 / 227 / 7
Регистрация: 06.07.2011
Сообщений: 512
29.05.2012, 00:51     Дано несколько точек с целочисленными координатами. Определить максимальное количество точек из них, лежащих на одной прямой. Если можно напечатать н #2
за эффективность не отвечаю. но ничего эффективнее 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 будет одинаков. поочередно переносим центр координат в каждую точку, считаем коэффициенты и частоту их повторений. частота наиболее популярного коэффициента и будет максимальным числом точек на одной прямой. самая большая частота для всех систем координат и есть ответ.

алгоритм можно значительно ускорить за счет "умных" структур и прерывания циклов когда надо.
lumpochka
0 / 0 / 0
Регистрация: 28.05.2012
Сообщений: 10
29.05.2012, 01:14  [ТС]     Дано несколько точек с целочисленными координатами. Определить максимальное количество точек из них, лежащих на одной прямой. Если можно напечатать н #3
Спасибо большое за ответ!!! Но здесь же на форуме уже нашла подходящий мне вариант программы. Не знаю только, можно ли в этой теме его опубликовать (программку-то, которую я нашла, не я писала) - вдруг ещё кому пригодится..
easybudda
Эксперт С++
9456 / 5469 / 927
Регистрация: 25.07.2009
Сообщений: 10,495
29.05.2012, 01:45     Дано несколько точек с целочисленными координатами. Определить максимальное количество точек из них, лежащих на одной прямой. Если можно напечатать н #4
Цитата Сообщение от lumpochka Посмотреть сообщение
Но здесь же на форуме уже нашла подходящий мне вариант программы. Не знаю только, можно ли в этой теме его опубликовать
Ссылки на пост будет вполне достаточно.
lumpochka
0 / 0 / 0
Регистрация: 28.05.2012
Сообщений: 10
29.05.2012, 03:02  [ТС]     Дано несколько точек с целочисленными координатами. Определить максимальное количество точек из них, лежащих на одной прямой. Если можно напечатать н #5
Определить минимальное подмножество точек, после удаления которых останутся точки лежащие на одной прямой
Yandex
Объявления
29.05.2012, 03:02     Дано несколько точек с целочисленными координатами. Определить максимальное количество точек из них, лежащих на одной прямой. Если можно напечатать н
Ответ Создать тему
Опции темы

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