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

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

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

C++ Определить минимальное подмножество точек, после удаления которых останутся точки лежащие на одной прямой
C++ Найти количество общих точек окружности и прямой
Определить количество точек, лежащих на заданной прямой C++
C++ Найти минимальный радиус шара, который будет охватывать все заданные точки(центр окружности лежит на одной из заданных точек)
Найти координаты точек пересечения прямой и окружности C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Catstail
Модератор
 Аватар для Catstail
21500 / 10253 / 1669
Регистрация: 12.02.2012
Сообщений: 17,139
06.07.2012, 11:32     Найти все подмножества точек, лежащих на одной прямой #2
Взять все пары точек (их будет Сn2 штук) и для каждой пары проверить все остальные точки на принадлежность прямой, проходящей через выбранную пару.

немного подождите...
Ксеня
Сообщений: n/a
06.07.2012, 12:20     Найти все подмножества точек, лежащих на одной прямой #3
а можно программу пожалуйста полностью?
Catstail
Модератор
 Аватар для Catstail
21500 / 10253 / 1669
Регистрация: 12.02.2012
Сообщений: 17,139
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     Найти все подмножества точек, лежащих на одной прямой
Ответ Создать тему
Опции темы

Текущее время: 01:57. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru