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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 11, средняя оценка - 4.73
Eleret
0 / 0 / 0
Регистрация: 28.12.2009
Сообщений: 5
28.12.2009, 05:47     Определить минимальное подмножество точек, после удаления которых останутся точки лежащие на одной прямой #1
Просьба по сути повторяет аналогичную из раздела о Паскале.

задано множество точек на плоскости,не лежащих на одной прямой.Определить минимальное подмножество точек,после удаления которых останутся точки лежащие на одной прямой.Задача сводится к поиску прямой на которой лежит максимальное число точек. Помогите, пожалуйста, решить, желательно через подпрограммы.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
28.12.2009, 05:47     Определить минимальное подмножество точек, после удаления которых останутся точки лежащие на одной прямой
Посмотрите здесь:

C++ Выбрать такие три точки из множества, не лежащие на одной прямой, которые составляют треугольник min площади
Определить, будут ли точки расположены на одной прямой C++
Определить, лежат ли точки на одной прямой C++
Определить будут ли заданные три точки расположены на одной прямой C++
Найти всевозможные группы по 3,4. точки, лежащие на одной прямой C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
TanT
эволюционирую потихоньку
 Аватар для TanT
464 / 462 / 43
Регистрация: 30.06.2009
Сообщений: 1,399
28.12.2009, 07:26     Определить минимальное подмножество точек, после удаления которых останутся точки лежащие на одной прямой #2
Сообщение было отмечено автором темы, экспертом или модератором как ответ
тестировать было не когда
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
#include <iostream>
using namespace std;
 
// поиск прямой на которой лежит  максимальное число точек. 
#define X 0
#define Y 1
#define nPoint sizeof(Points)/2/sizeof(Points[0][0])
 
const double Points[][2] = {
    { 1.0, 1.0},
    { 12.0, 12.0},
    { 14.0, 14.0},
    { 15.0, 15.0},
    { 2.0, 3.0},
    { 4.0, 7.0},
    { 5.0, 9.0}
}; 
 
// y=kx+b
double Calc_K(double x1, double y1, double x2, double y2)
{   
    return (y1-y2)/(x1-x2);
}
 
// y=kx+b
double Calc_B(double x1, double y1, double x2, double y2)
{   
    return (y2*x1-y1*x2)/(x1-x2);
}
 
int main ()
{
 
    double k,b, finder[2][2];
    int counter, temp=-1;
 
    for (int i=1; i<nPoint; i++)
    {
        if(Points[i-1][X]==Points[i][X])  continue;
 
        k=Calc_K(Points[i-1][X], Points[i-1][Y], Points[i][X], Points[i][Y]);
        b=Calc_B(Points[i-1][X], Points[i-1][Y], Points[i][X], Points[i][Y]);
        counter=2;
        for (int j=i+1; j<nPoint; j++)
        {
            if(Points[j][Y]==k*Points[j][X]+b) ++counter;
        }
        if(counter>temp) 
        { 
            temp=counter; 
            finder[0][X]=Points[i-1][X]; finder[1][X]=Points[i][X];
            finder[0][Y]=Points[i-1][Y]; finder[1][Y]=Points[i][Y];
        }
    } // for (int i=1;
 
    cout<<"points: "<<temp<<" line:: x1: "<<finder[0][X]<<" y1: "<<finder[0][Y]
            <<" x2: "<<finder[1][X]<<" y2: "<<finder[1][Y]<<endl;
    system("pause");
    return 0;
}
Eleret
0 / 0 / 0
Регистрация: 28.12.2009
Сообщений: 5
28.12.2009, 08:57  [ТС]     Определить минимальное подмножество точек, после удаления которых останутся точки лежащие на одной прямой #3
Ага, здорово...
А можно еще сделать так, чтобы самому множество задавать?)
TanT
эволюционирую потихоньку
 Аватар для TanT
464 / 462 / 43
Регистрация: 30.06.2009
Сообщений: 1,399
28.12.2009, 14:05     Определить минимальное подмножество точек, после удаления которых останутся точки лежащие на одной прямой #4
можно
Eleret
0 / 0 / 0
Регистрация: 28.12.2009
Сообщений: 5
28.12.2009, 15:31  [ТС]     Определить минимальное подмножество точек, после удаления которых останутся точки лежащие на одной прямой #5
Напишите, пожалуйста, как)
TanT
эволюционирую потихоньку
 Аватар для TanT
464 / 462 / 43
Регистрация: 30.06.2009
Сообщений: 1,399
28.12.2009, 16:26     Определить минимальное подмножество точек, после удаления которых останутся точки лежащие на одной прямой #6
Сообщение было отмечено автором темы, экспертом или модератором как ответ
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
#include <iostream>
using namespace std;
 
// поиск прямой на которой лежит  максимальное число точек. 
#define X 0
#define Y 1
 
// y=kx+b
double Calc_K(double x1, double y1, double x2, double y2)
{       
    return (y1-y2)/(x1-x2);
}
 
// y=kx+b
double Calc_B(double x1, double y1, double x2, double y2)
{       
    return (y2*x1-y1*x2)/(x1-x2);
}
 
int main ()
{
 
    double k,b, finder[2][2];
    int counter, temp=-1, n;
 
    cout<<"Enter number points( n>2 ): "; cin>>n;
    if(n<=2) { cout<<"Number points is little"; system("pause");    return 0;}
 
    double ** Points = new  double* [n];
    for (int i=0; i<n; i++)
    {
        Points[i]= new double [2];
        cout<<"Enter pair["<<i+1<<"]:\nx: "; cin>>Points[i][X];
        cout<<"y: ";                                                 cin>>Points[i][Y];     
    }   
 
    for (int i=1; i<n; i++)
    {       
        //if(Points[i-1][X]==Points[i][X])  continue;
 
        k=Calc_K(Points[i-1][X], Points[i-1][Y], Points[i][X], Points[i][Y]);
        b=Calc_B(Points[i-1][X], Points[i-1][Y], Points[i][X], Points[i][Y]);
        counter=2;
        for (int j=i+1; j<n; j++)
        {
            if(Points[j][Y]==k*Points[j][X]+b) ++counter;
        }
        if(counter>temp) 
        { 
            temp=counter; 
            finder[0][X]=Points[i-1][X]; finder[1][X]=Points[i][X];
            finder[0][Y]=Points[i-1][Y]; finder[1][Y]=Points[i][Y];
        }
    } // for (int i=1;
 
    cout<<"points: "<<temp<<"\n line:: x1: "<<finder[0][X]<<" y1: "<<finder[0][Y]
    <<"\n        x2: "<<finder[1][X]<<" y2: "<<finder[1][Y]<<endl;
    system("pause");
    return 0;
}
Eleret
0 / 0 / 0
Регистрация: 28.12.2009
Сообщений: 5
28.12.2009, 21:15  [ТС]     Определить минимальное подмножество точек, после удаления которых останутся точки лежащие на одной прямой #7
Ага, количество точек, которые нужно убрать уже очевидно.
Большое спасибо!
Eleret
0 / 0 / 0
Регистрация: 28.12.2009
Сообщений: 5
05.01.2010, 09:39  [ТС]     Определить минимальное подмножество точек, после удаления которых останутся точки лежащие на одной прямой #8
А можно все это для <conio.h> + <stdio.h>?
Protected_fleur
0 / 0 / 0
Регистрация: 29.06.2011
Сообщений: 77
29.06.2011, 19:32     Определить минимальное подмножество точек, после удаления которых останутся точки лежащие на одной прямой #9
Было бы здорово, если бы написано было на си...
nameless
Эксперт C++
 Аватар для nameless
289 / 288 / 14
Регистрация: 16.06.2009
Сообщений: 486
29.06.2011, 19:54     Определить минимальное подмножество точек, после удаления которых останутся точки лежащие на одной прямой #10
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Protected_fleur,

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
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
 
// поиск прямой на которой лежит  максимальное число точек. 
#define X 0
#define Y 1
 
// y=kx+b
double Calc_K(double x1, double y1, double x2, double y2)
{       
        return (y1-y2)/(x1-x2);
}
 
// y=kx+b
double Calc_B(double x1, double y1, double x2, double y2)
{       
        return (y2*x1-y1*x2)/(x1-x2);
}
 
int main ()
{
 
        double k,b, finder[2][2];
        int counter, temp=-1, n;
 
        printf("Enter number points( n>2 ): ");
        scanf("%d", &n);
        if(n<=2) { printf("Number points is little"); _getch(); _exit(EXIT_FAILURE);}
 
        double ** Points = (double**)malloc(n * sizeof(double*));
        for (int i=0; i<n; i++)
        {
                Points[i]= (double*)malloc(2 * sizeof(double));
                printf("Enter pair[%d]:\nx: ", i + 1); scanf("%f", &Points[i][X]);
                printf("y: ");                                                                                             scanf("%f", &Points[i][Y]) ;      
        }       
 
        for (int i=1; i<n; i++)
        {               
                //if(Points[i-1][X]==Points[i][X])  continue;
 
                k=Calc_K(Points[i-1][X], Points[i-1][Y], Points[i][X], Points[i][Y]);
                b=Calc_B(Points[i-1][X], Points[i-1][Y], Points[i][X], Points[i][Y]);
                counter=2;
                for (int j=i+1; j<n; j++)
                {
                        if(Points[j][Y]==k*Points[j][X]+b) ++counter;
                }
                if(counter>temp) 
                { 
                        temp=counter; 
                        finder[0][X]=Points[i-1][X]; finder[1][X]=Points[i][X];
                        finder[0][Y]=Points[i-1][Y]; finder[1][Y]=Points[i][Y];
                }
        } // for (int i=1;
 
        printf("points: %d\n line:: x1: %f y1: %f\nx2: %f y2: %f", temp, finder[0][X], finder[0][Y], finder[1][X], finder[1][Y]);
 
        _getch();
        return 0;
}
Protected_fleur
0 / 0 / 0
Регистрация: 29.06.2011
Сообщений: 77
29.06.2011, 20:02     Определить минимальное подмножество точек, после удаления которых останутся точки лежащие на одной прямой #11
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
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
 
// поиск прямой на которой лежит  максимальное число точек. 
#define X 0
#define Y 1
 
// y=kx+b
double Calc_K(double x1, double y1, double x2, double y2)
{       
        return (y1-y2)/(x1-x2);
}
 
// y=kx+b
double Calc_B(double x1, double y1, double x2, double y2)
{       
        return (y2*x1-y1*x2)/(x1-x2);
}
 
int main ()
{
 
        double k,b, finder[2][2];
        int counter, temp=-1, n;
 
        printf("Enter number points( n>2 ): ");
        scanf("%d", &n);
        if(n<=2) { printf("Number points is little"); _getch(); _exit(EXIT_FAILURE);}
 
        double ** Points = (double*)malloc(n * sizeof(double*));
        for (int i=0; i<n; i++)
        {
                Points[i]= (double*)malloc(2 * sizeof(double));
                printf("Enter pair[%d]:\nx: ", i + 1); 
                scanf("%f", &Points[i][X]);
                printf("y: ");              
        }       
 
        for (int i=1; i<n; i++)
        {               
                //if(Points[i-1][X]==Points[i][X])  continue;
 
                k=Calc_K(Points[i-1][X], Points[i-1][Y], Points[i][X], Points[i][Y]);
                b=Calc_B(Points[i-1][X], Points[i-1][Y], Points[i][X], Points[i][Y]);
                counter=2;
                for (int j=i+1; j<n; j++)
                {
                        if(Points[j][Y]==k*Points[j][X]+b) ++counter;
                }
                if(counter>temp) 
                { 
                        temp=counter; 
                        finder[0][X]=Points[i-1][X]; finder[1][X]=Points[i][X];
                        finder[0][Y]=Points[i-1][Y]; finder[1][Y]=Points[i][Y];
                }
        } // for (int i=1;
 
        printf("points: %d\n line:: x1: %f y1: %f\nx2: %f y2: %f", temp, finder[0][X], finder[0][Y], finder[1][X], finder[1][Y]);
 
        _getch();
        return 0;
}


Компилятор ругается на эту строчку((((
я сама-то в ней неособо разбираюсь((((
double ** Points = (double*)malloc(n * sizeof(double*));
nameless
Эксперт C++
 Аватар для nameless
289 / 288 / 14
Регистрация: 16.06.2009
Сообщений: 486
29.06.2011, 20:04     Определить минимальное подмножество точек, после удаления которых останутся точки лежащие на одной прямой #12
Protected_fleur,
Цитата Сообщение от Protected_fleur Посмотреть сообщение
double ** Points = (double*)malloc(n * sizeof(double*));
На

C
1
double ** Points = (double**)malloc(n * sizeof(double*));
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
30.06.2011, 16:10     Определить минимальное подмножество точек, после удаления которых останутся точки лежащие на одной прямой
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
Protected_fleur
0 / 0 / 0
Регистрация: 29.06.2011
Сообщений: 77
30.06.2011, 16:10     Определить минимальное подмножество точек, после удаления которых останутся точки лежащие на одной прямой #13
не могу найти ошибку((( не считает...выдает нули и все((((


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
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
 
// поиск прямой на которой лежит  максимальное число точек. 
#define X 0
#define Y 1
 
// y=kx+b
double Calc_K(double x1, double y1, double x2, double y2)
{       
        return (y1-y2)/(x1-x2);
}
 
// y=kx+b
double Calc_B(double x1, double y1, double x2, double y2)
{       
        return (y2*x1-y1*x2)/(x1-x2);
}
 
int main ()
{
 
        double k,b, finder[2][2];
        int counter, temp=-1, n;
 
        printf("Enter number points( n>2 ): ");
        scanf("%d", &n);
        if(n<=2) { 
        printf("Number points is little"); _getch(); _exit(EXIT_FAILURE);}
 
        double ** Points = (double**)malloc(n * sizeof(double*));
        for (int i=0; i<n; i++)
        {
                Points[i]= (double*)malloc(2 * sizeof(double));
                printf("Enter pair[%d]:\n x: ", i + 1); 
                scanf("%f", &Points[i][X]);
                printf("y: ");              
        }       
 
        for (int i=1; i<n; i++)
        {               
                //if(Points[i-1][X]==Points[i][X])  continue;
 
                k=Calc_K(Points[i-1][X], Points[i-1][Y], Points[i][X], Points[i][Y]);
                b=Calc_B(Points[i-1][X], Points[i-1][Y], Points[i][X], Points[i][Y]);
                counter=2;
                for (int j=i+1; j<n; j++)
                {
                        if(Points[j][Y]==k*Points[j][X]+b) ++counter;
                }
                
                if(counter>temp) 
                { 
                        temp=counter; 
                        finder[0][X]=Points[i-1][X]; finder[1][X]=Points[i][X];
                        finder[0][Y]=Points[i-1][Y]; finder[1][Y]=Points[i][Y];
                }
        } // for (int i=1;
 
        printf("points: %d\n line:: x1: %f y1: %f\nx2: %f y2: %f", temp, finder[0][X], finder[0][Y], finder[1][X], finder[1][Y]);
        return 0;
        _getch();
}
Добавлено через 18 часов 38 минут
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
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
 
// поиск прямой на которой лежит  максимальное число точек. 
#define X 0
#define Y 1
 
// y=kx+b
double Calc_K(double x1, double y1, double x2, double y2)
{       
        return (y1-y2)/(x1-x2);
}
 
// y=kx+b
double Calc_B(double x1, double y1, double x2, double y2)
{       
        return (y2*x1-y1*x2)/(x1-x2);
}
 
int main ()
{
 
        double k,b, finder[2][2];
        int counter, temp=-1, n;
 
        printf("Enter number points( n>2 ): ");
        scanf("%d", &n);
        if(n<=2) { 
        printf("Number points is little");  
        _getch();
        return 0;}
 
        double ** Points = (double**)malloc(n * sizeof(double*));
        for (int i=0; i<n; i++)
        {
                Points[i]= (double*)malloc(2 * sizeof(double));
                printf("Enter pair[%d]:\n x: ", i + 1); 
                scanf("%f", &Points[i][X]);
                printf("y: ");              
        }       
 
        for (int i=1; i<n; i++)
        {               
                //if(Points[i-1][X]==Points[i][X])  continue;
 
                k=Calc_K(Points[i-1][X], Points[i-1][Y], Points[i][X], Points[i][Y]);
                b=Calc_B(Points[i-1][X], Points[i-1][Y], Points[i][X], Points[i][Y]);
                counter=2;
                for (int j=i+1; j<n; j++)
                {
                        if(Points[j][Y]==k*Points[j][X]+b) ++counter;
                }
                
                if(counter>temp) 
                { 
                        temp=counter; 
                        finder[0][X]=Points[i-1][X]; 
                        finder[1][X]=Points[i][X];
                        finder[0][Y]=Points[i-1][Y]; 
                        finder[1][Y]=Points[i][Y];
                }
        } // for (int i=1;
 
        printf("points: %d\n line:: x1: %f y1: %f\nx2: %f y2: %f", temp, finder[0][X], finder[0][Y], finder[1][X], finder[1][Y]);
        _getch();
        return 0;
}
Помогите пожалуйста!!! почему не считает(((
Yandex
Объявления
30.06.2011, 16:10     Определить минимальное подмножество точек, после удаления которых останутся точки лежащие на одной прямой
Ответ Создать тему
Опции темы

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