0 / 0 / 0
Регистрация: 28.05.2012
Сообщений: 10
1

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

28.05.2012, 23:41. Показов 4217. Ответов 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()
{}
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
28.05.2012, 23:41
Ответы с готовыми решениями:

Дано n точек, определить какое максимальное количество точек лежит на одной прямой
Дано n точек, определить какое максимальное количество точек лежит на одной прямой.

Дано n точек, определить какое максимальное количество точек лежит на одной прямой
Дано n точек, определить какое максимальное количество точек лежит на одной прямой. Решите...

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

Определить количество точек с целочисленными координатами, лежащих внутри окружности радиусом R с центром в точке (х0, у0).
Определить количество точек с целочисленными координатами, лежащих внутри окружности радиусом R с...

4
385 / 229 / 12
Регистрация: 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 будет одинаков. поочередно переносим центр координат в каждую точку, считаем коэффициенты и частоту их повторений. частота наиболее популярного коэффициента и будет максимальным числом точек на одной прямой. самая большая частота для всех систем координат и есть ответ.

алгоритм можно значительно ускорить за счет "умных" структур и прерывания циклов когда надо.
1
0 / 0 / 0
Регистрация: 28.05.2012
Сообщений: 10
29.05.2012, 01:14  [ТС] 3
Спасибо большое за ответ!!! Но здесь же на форуме уже нашла подходящий мне вариант программы. Не знаю только, можно ли в этой теме его опубликовать (программку-то, которую я нашла, не я писала) - вдруг ещё кому пригодится..
0
Модератор
Эксперт PythonЭксперт JavaЭксперт CЭксперт С++
11895 / 7267 / 1721
Регистрация: 25.07.2009
Сообщений: 13,310
29.05.2012, 01:45 4
Цитата Сообщение от lumpochka Посмотреть сообщение
Но здесь же на форуме уже нашла подходящий мне вариант программы. Не знаю только, можно ли в этой теме его опубликовать
Ссылки на пост будет вполне достаточно.
1
0 / 0 / 0
Регистрация: 28.05.2012
Сообщений: 10
29.05.2012, 03:02  [ТС] 5
Определить минимальное подмножество точек, после удаления которых останутся точки лежащие на одной прямой
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
29.05.2012, 03:02
Помогаю со студенческими работами здесь

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

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

Подсчитать количество точек с целочисленными координатами, лежащих внутри этого треугольника...
Целые точки Ограничение времени 1 секунда Ограничение памяти 64Mb Ввод стандартный ввод или...

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


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2023, CyberForum.ru