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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 13, средняя оценка - 4.77
Ксеня
Сообщений: n/a
#1

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

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

на плоскости задано множество точек. Найти все подмножества точек, лежащих на одной прямой.
помогите пожалуйста решить
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
06.07.2012, 10:44     Найти все подмножества точек, лежащих на одной прямой
Посмотрите здесь:

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

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

Определить количество точек, лежащих на заданной прямой - C++
Создайте структуру Прямая с элементами a, b - коэффициенты уравнения y=ax+b и структуру Точка с элементами x, y - координаты точки. Дана...

Определить взаимное расположение трех точек на плоскости (совпадают, на одной прямой, создают треугольник) - C++
точка на плоскости задается своими координатами. Создать программу, которая определяет взаимное расположение трех точек на плоскости...

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

Найти минимальный радиус шара, который будет охватывать все заданные точки(центр окружности лежит на одной из заданных точек) - C++
есть программа, проблема в передаче массива в функцию a #include "stdio.h" #include "conio.h" #include "math.h" #include...

Найти все возможные подмножества из данного множества - C++
Необходимо написать программу, выводящую все возможные подмножества из данного множества. Выглядить должно примерно так: Массив на...

Найти количество общих точек окружности и прямой - C++
Решить задачу в С++ Помогите пожалуйста =) Дана окружность и прямая. Окружность задается уранвением r²=x²+y². Уравнение прямой y=ax+b....

Найти координаты точек пересечения прямой и окружности - C++
Найти координаты точек пересечения прямой y=kx+b и окружности радиуса R с центром в начале координат. В каких координатных четвертях...

Найти всевозможные группы по 3,4. точки, лежащие на одной прямой - C++
На плоскости заданы своими целочисленными координатами n точек. Найти всевозможные группы по 3,4... точки, лежащие на одной прямой. ...

Верно ли, что для любой пары точек из множества все оставшиеся точки лежат по одну сторону от прямой, проведённой через эту пару - C++
Даны действительные числа x1,....x15, y1,....y15, которые рассматриваются как координаты 15 точек на плоскости. Верно ли, что для каждой из...

Определить, лежат ли три точки A, B, C на одной прямой. Если нет, найти угол ABC - C++
Даны три точки A(x_1, y_1), \, B(x_2, y_2), \, C(x_3, y_3) Определить будут ли они расположены на одной прямой. Если нет, то...


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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Catstail
Модератор
22510 / 10915 / 1774
Регистрация: 12.02.2012
Сообщений: 18,063
06.07.2012, 11:32     Найти все подмножества точек, лежащих на одной прямой #2
Взять все пары точек (их будет Сn2 штук) и для каждой пары проверить все остальные точки на принадлежность прямой, проходящей через выбранную пару.

немного подождите...
Ксеня
Сообщений: n/a
06.07.2012, 12:20     Найти все подмножества точек, лежащих на одной прямой #3
а можно программу пожалуйста полностью?
Catstail
Модератор
22510 / 10915 / 1774
Регистрация: 12.02.2012
Сообщений: 18,063
06.07.2012, 12:55     Найти все подмножества точек, лежащих на одной прямой #4
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Вот программа... Но с одним НО: она будет работать только для таких множеств, в которых число точек, лежащих на одной прямой, не превышает 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;
}
Да, поскольку любые две точки лежат на одной прямой, программа не выводит двухэлементные множества. И ещё: не следует задавать
одинаковые точки (впрочем, это легко распознать программно).
Миниатюры
Найти все подмножества точек, лежащих на одной прямой  
Yandex
Объявления
06.07.2012, 12:55     Найти все подмножества точек, лежащих на одной прямой
Ответ Создать тему
Опции темы

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