Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 11, средняя оценка - 4.73
Eleret
0 / 0 / 0
Регистрация: 28.12.2009
Сообщений: 5
#1

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

28.12.2009, 05:47. Просмотров 1618. Ответов 12
Метки нет (Все метки)

Просьба по сути повторяет аналогичную из раздела о Паскале.

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

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

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

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

Определить, лежат ли точки на одной прямой - C++
ВСЕМ ПРИВЕТ!!!!!!!!ПОМОГИТЕ КТО-НИБУДЬ СПРАВИТЬСЯ С ЗАДАЧЕЙ НА С++.рЕШИТЕ ПОЖАЛУЙСТА ВОТ УСЛОВИЕ- "Заданы три точки на плоскости: M с...

Определить расположены ли точки на одной прямой - C++
Даны три точки А(x1, y1), В(x2, y2), С(x3, y3). Определить будут ли они расположены на одной прямой. Если нет, то вычислить угол АВС.

Определить, будут ли точки расположены на одной прямой - C++
Помогите пожалуйста надо срочно решить эти задачки: 1. Дано натуральное число n. Среди чисел 1, ..., n найти такие, запись которых...

12
TanT
эволюционирую потихоньку
466 / 464 / 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;
}
0
Eleret
0 / 0 / 0
Регистрация: 28.12.2009
Сообщений: 5
28.12.2009, 08:57  [ТС] #3
Ага, здорово...
А можно еще сделать так, чтобы самому множество задавать?)
0
TanT
эволюционирую потихоньку
466 / 464 / 43
Регистрация: 30.06.2009
Сообщений: 1,399
28.12.2009, 14:05 #4
можно
0
Eleret
0 / 0 / 0
Регистрация: 28.12.2009
Сообщений: 5
28.12.2009, 15:31  [ТС] #5
Напишите, пожалуйста, как)
0
TanT
эволюционирую потихоньку
466 / 464 / 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;
}
2
Eleret
0 / 0 / 0
Регистрация: 28.12.2009
Сообщений: 5
28.12.2009, 21:15  [ТС] #7
Ага, количество точек, которые нужно убрать уже очевидно.
Большое спасибо!
0
Eleret
0 / 0 / 0
Регистрация: 28.12.2009
Сообщений: 5
05.01.2010, 09:39  [ТС] #8
А можно все это для <conio.h> + <stdio.h>?
0
Protected_fleur
0 / 0 / 0
Регистрация: 29.06.2011
Сообщений: 77
29.06.2011, 19:32 #9
Было бы здорово, если бы написано было на си...
0
nameless
Эксперт С++
334 / 298 / 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;
}
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*));
0
nameless
Эксперт С++
334 / 298 / 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*));
1
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;
}
Помогите пожалуйста!!! почему не считает(((
0
30.06.2011, 16:10
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
30.06.2011, 16:10
Привет! Вот еще темы с ответами:

Определить лежат ли три точки на одной прямой - C++
Добро времени суток уважаемые программисты.Суть такова.Нужно,чтобы я вводил координаты,а программа выдавала мне лежат ли они на одной...

Определить будут ли заданные три точки расположены на одной прямой - C++
1) f(x){0; если x&lt;=1 x+6 В противном случае 2)Даны действительные числа x и y, не равные друг другу. Меньшее из этих чисел...

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

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


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

Или воспользуйтесь поиском по форуму:
13
Ответ Создать тему
Опции темы

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