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

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

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

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

28.05.2012, 23:41. Просмотров 1270. Ответов 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++
Создайте структуру Прямая с элементами a, b - коэффициенты уравнения y=ax+b и структуру Точка с элементами x, y - координаты точки. Дана...

вычислите количество точек с целочисленными координатами,находящиеся в круге - C++
вычислите количество точек с целочисленными координатами,находящиеся в круге радиуса R (R&gt;0)

Найти все подмножества точек, лежащих на одной прямой - C++
на плоскости задано множество точек. Найти все подмножества точек, лежащих на одной прямой. помогите пожалуйста решить

Найти количество точек с целочисленными координатами внутри заданного отрезка - C++
как мне найти количество точек с целочисленными координатами внутри отрезка. Вам даны начальные точки отрезка(координаты)-x и y; и...

Количество точек с целочисленными координатами внутри (не включая границ) произвольного многоугольника - C++
Есть вот такая задача. Координаты вершин подаются в порядке обхода по часовой стрелке, многоугольник может быть и невыпуклым. Решение...

Найти в бинарном файле все пары точек, лежащих с точкой d на одной прямой - C++
В файле заданы множество точек А и точка d вне его. Найти все пары точек, лежащих с точкой d на одной прямой. с++ срочно!!!

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
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
Модератор
Эксперт CЭксперт С++
9530 / 5523 / 932
Регистрация: 25.07.2009
Сообщений: 10,602
29.05.2012, 01:45 #4
Цитата Сообщение от lumpochka Посмотреть сообщение
Но здесь же на форуме уже нашла подходящий мне вариант программы. Не знаю только, можно ли в этой теме его опубликовать
Ссылки на пост будет вполне достаточно.
lumpochka
0 / 0 / 0
Регистрация: 28.05.2012
Сообщений: 10
29.05.2012, 03:02  [ТС] #5
Определить минимальное подмножество точек, после удаления которых останутся точки лежащие на одной прямой
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
29.05.2012, 03:02
Привет! Вот еще темы с ответами:

Вычислить количество точек с целочисленными координатами, попадающими в круг радиуса R>0 с центром в начале координат - C++
Вот тут дали задания и не знаю как решить....я думаю есть добрые люди???=))) Вычислить количество точек с целочисленными координатами,...

Вычислить k-количество точек с целочисленными координатами, попадающих в круг ра-диуса R(R>0) с центром в начале координат - C++
Очень нужна ваша помощь. Написала программу , но не уверенна в ее правильности. Можете посмотреть и исправить ,если что-то не так . Заранее...

Определить, сколько точек с целочисленными координатами попадают в круг заданного радиуса с центром в начале координат - C++
Вводится радиус круга R. Определить, сколько точек с целочисленными координатами попадают в круг заданного радиуса с центром в начале...

Дано множество точек на плоскости, заданных полярными координатами. Получить декартовы координаты этих точек - C++
Получилось сделать для координаты одной точки, а как сделать для множества точек, через цикл или массив? #include &lt;stdio.h&gt; #include...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
29.05.2012, 03:02
Ответ Создать тему
Опции темы

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