Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.97/29: Рейтинг темы: голосов - 29, средняя оценка - 4.97
Ксеня

Найти все подмножества точек, лежащих на одной прямой

06.07.2012, 10:44. Показов 5905. Ответов 3
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
на плоскости задано множество точек. Найти все подмножества точек, лежащих на одной прямой.
помогите пожалуйста решить
Лучшие ответы (1)
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
06.07.2012, 10:44
Ответы с готовыми решениями:

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

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

Перечислить все различные максимальные подмножества точек, лежащих на одной прямой
Добрый день Хочу попросить форумчан в составлении алгоритма, ибо самому не получается Задача: Задано множество точек на плоскости....

3
Супер-модератор
Эксперт функциональных языков программированияЭксперт Python
 Аватар для Catstail
38180 / 21115 / 4307
Регистрация: 12.02.2012
Сообщений: 34,722
Записей в блоге: 14
06.07.2012, 11:32
Взять все пары точек (их будет Сn2 штук) и для каждой пары проверить все остальные точки на принадлежность прямой, проходящей через выбранную пару.

немного подождите...
1
Ксеня
06.07.2012, 12:20
а можно программу пожалуйста полностью?
Супер-модератор
Эксперт функциональных языков программированияЭксперт Python
 Аватар для Catstail
38180 / 21115 / 4307
Регистрация: 12.02.2012
Сообщений: 34,722
Записей в блоге: 14
06.07.2012, 12:55
Лучший ответ Сообщение было отмечено Памирыч как решение

Решение

Вот программа... Но с одним НО: она будет работать только для таких множеств, в которых число точек, лежащих на одной прямой, не превышает 32. В противном случае нужны доработки. Пойдет?

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include "iostream.h"
#include "math.h"
 
int main(int argc, char* argv[])
{
 
    int n,i,j,k,p=0,kb,q;
 
    unsigned long *SetP,CurrSet;
 
    double *X,*Y;
 
    cout << "n=";
    cin >> n;
 
    X=new double[n];
    Y=new double[n];
 
        SetP=new unsigned long[n];
 
       for (i=0; i<n; i++)
    {
        cout << "X[" << i << "]= ";
        cin >> X[i];
        cout << "Y[" << i << "]= ";
        cin >> Y[i];
    }
    
    for (i=0; i<n; i++) SetP[i]=0;
 
    for (i=0; i<n-1; i++)
        for (j=i+1; j<n; j++)
        {
            CurrSet=0;
            CurrSet=CurrSet | (1 << i);
            CurrSet=CurrSet | (1 << j);
            kb=2;
 
            for (k=0; k<n; k++)
            {
 
                if ((k != i) && (k != j))
                    if (fabs((X[k]-X[i])*(Y[j]-Y[i])-(X[j]-X[i])*(Y[k]-Y[i])) <= 1.0E-9)
                    {
                                           CurrSet=CurrSet | (1 << k); 
                       kb++;
                    }
 
            }
 
            if (kb > 2)
            {
               q=0;
               for (k=0; k<p; k++)
                    if (CurrSet == SetP[k])
                    {
                      q=-1;
                      break;
                    }
                           if (q == 0) SetP[p++]=CurrSet;
            }
 
        }
 
    for (i=0; i<p; i++) 
    {
        for (j=0; j <= 31; j++)
            if (SetP[i] & (1 << j)) cout << j << " ";
        cout << endl;
    }
 
    delete [] X;
        delete [] Y;
    delete [] SetP;
 
    return 0;
}
Да, поскольку любые две точки лежат на одной прямой, программа не выводит двухэлементные множества. И ещё: не следует задавать
одинаковые точки (впрочем, это легко распознать программно).
Миниатюры
Найти все подмножества точек, лежащих на одной прямой  
1
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
06.07.2012, 12:55
Помогаю со студенческими работами здесь

Найти уравнение прямой, делящей множество точек на 2 равномощных подмножества
На плоскости N различных точек заданы своими координатами. Найти уравнение прямой, делящей это множество точек на 2 равномощных...

Найти количество точек, лежащих выше прямой
Заданы координаты N точек и уравнение прямой. Найти количество точек, лежащих выше прямой.

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

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

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


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

Или воспользуйтесь поиском по форуму:
4
Ответ Создать тему
Новые блоги и статьи
SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++
8Observer8 10.03.2026
Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:
Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE
8Observer8 10.03.2026
Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .
Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки
Neotwalker 08.03.2026
Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .
Модульная разработка через nuget packages
DevAlt 07.03.2026
Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .
Модульный подход на примере F#
DevAlt 06.03.2026
В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .
Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование
8Observer8 05.03.2026
Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .
SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D
8Observer8 04.03.2026
Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .
SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий
8Observer8 02.03.2026
Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip Сканируйте QR-код на мобильном и вы увидите, что появится джойстик для управления главным героем. . . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru