Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.67
Death99_99
0 / 0 / 0
Регистрация: 06.05.2013
Сообщений: 18
#1

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

06.05.2013, 08:37. Просмотров 1219. Ответов 16
Метки нет (Все метки)

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

Добавлено через 16 минут
Вот начало программы, а как реализовать цикл нахождения не могу понять...
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
#include "stdafx.h"
#include <stdio.h>
#include <iostream>
#include <fstream>
#include <cmath>
#include <locale>
using namespace std;
int x,y,k,*arrx,*arry;
 
int _tmain(int argc, _TCHAR* argv[])
{
    arrx=new int;
    arry=new int;
    setlocale(LC_ALL,"Russian");
    cout << "Введите Количество точек, лежащих в координатной плоскости:" << '\n';
    cin >> k;
    cout << "Вводите координаты точек по порядку:" << '\n';
    for (int i=0; i<k; i++)
    {
        cin >> arrx[i] >> arry[i];
        cout << '\n';
    }
    for (int i=0; i<k; i++)
    {
        cout << "x=" << arrx[i] << " " << "y=" << arry[i] << '\n';
    }
    
 
    system ("pause");
    return 0;
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
06.05.2013, 08:37
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Найти всевозможные группы по 3,4. точки, лежащие на одной прямой (C++):

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

Из множества точек выбрать три точки, не лежащие на одной прямой, составляющие треугольник наименьшей площади
Разработать программу выбора из заданного на плоскости множества точек N (N...

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

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

Принадлежат ли точки одной прямой
Ребят, не могу понять как в C++ написать программу к задаче: Даны три точки,...

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

16
Miwa123
37 / 37 / 22
Регистрация: 16.04.2013
Сообщений: 319
Записей в блоге: 1
06.05.2013, 11:37 #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
#include <iostream>
using namespace std;
bool uravnenie(double x1,double y1,double x2,double y2,double &K,double &B);
int main()
{
    double k,*arrx,*arry,K,B;
    arrx=new double;
    arry=new double;
    setlocale(LC_ALL,"Russian");
    cout << "Введите Количество точек, лежащих в координатной плоскости:" << '\n';
    cin >> k;
    cout << "Вводите координаты точек по порядку:" << '\n';
    for (int i=0; i<k; i++)
    {
        cin >> arrx[i] >> arry[i];
        cout << '\n';
    }
  
    
    for(int i=0;i<k;i++)
    {
    
        for(int j=i+1;j<k;j++)
        {
         uravnenie(arrx[i],arry[i],arrx[j],arry[j],K,B);
                  for(int m=0;m<k;m++)
                  {
                      if(m==i || m==j)continue;
                      if(arry[m]==K*arrx[m]+B)
                      {
                          cout << "на прямой, которая проведена через точками с нормерами " << i+1 << " - " << j+1 << " лежит точка " << m+1 << endl;
                      }
                  }
        }
    
    }
    
    system ("pause");
    return 0;
}
 
bool uravnenie(double x1,double y1,double x2,double y2,double &K,double &B)
{
    
    
    
    if((y1-y2)==0 || (x1-x2)==0)
        K=0;
    else
    K=(y1-y2)/(x1-x2);
    B=y1-K*x1;
    
    return true;
}
1
Death99_99
0 / 0 / 0
Регистрация: 06.05.2013
Сообщений: 18
06.05.2013, 11:50  [ТС] #3
Цитата Сообщение от Miwa123 Посмотреть сообщение
Кликните здесь для просмотра всего текста
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
#include <iostream>
using namespace std;
bool uravnenie(double x1,double y1,double x2,double y2,double &K,double &B);
int main()
{
    double k,*arrx,*arry,K,B;
    arrx=new double;
    arry=new double;
    setlocale(LC_ALL,"Russian");
    cout << "Введите Количество точек, лежащих в координатной плоскости:" << '\n';
    cin >> k;
    cout << "Вводите координаты точек по порядку:" << '\n';
    for (int i=0; i<k; i++)
    {
        cin >> arrx[i] >> arry[i];
        cout << '\n';
    }
  
    
    for(int i=0;i<k;i++)
    {
    
        for(int j=i+1;j<k;j++)
        {
         uravnenie(arrx[i],arry[i],arrx[j],arry[j],K,B);
                  for(int m=0;m<k;m++)
                  {
                      if(m==i || m==j)continue;
                      if(arry[m]==K*arrx[m]+B)
                      {
                          cout << "на прямой, которая проведена через точками с нормерами " << i+1 << " - " << j+1 << " лежит точка " << m+1 << endl;
                      }
                  }
        }
    
    }
    
    system ("pause");
    return 0;
}
 
bool uravnenie(double x1,double y1,double x2,double y2,double &K,double &B)
{
    
    
    
    if((y1-y2)==0 || (x1-x2)==0)
        K=0;
    else
    K=(y1-y2)/(x1-x2);
    B=y1-K*x1;
    
    return true;
}
Появляется вот такая ошибка.
0
Миниатюры
Найти всевозможные группы по 3,4. точки, лежащие на одной прямой  
Bend3r
149 / 136 / 35
Регистрация: 29.07.2012
Сообщений: 709
06.05.2013, 12:01 #4
Цитата Сообщение от Death99_99 Посмотреть сообщение
Появляется вот такая ошибка.
Скорей всего ты где-то сделал точку остановы. Просто перезапусти студию.
1
Death99_99
0 / 0 / 0
Регистрация: 06.05.2013
Сообщений: 18
06.05.2013, 12:14  [ТС] #5
Цитата Сообщение от Bend3r Посмотреть сообщение
Скорей всего ты где-то сделал точку остановы. Просто перезапусти студию.
Не помогло. Заметил такую особенность. Такая ошибка вылетает если количество точек более 5 и есть хотя бы 3 точки лежащие на одной прямой.
До 5 точек все прекрасно работает.
0
Bend3r
149 / 136 / 35
Регистрация: 29.07.2012
Сообщений: 709
06.05.2013, 12:21 #6
У меня программа вообще не работает. Обьяснить еще раз подробно задание попытаюсь решить ваше задание.(Только подробно)
0
kamre
127 / 131 / 11
Регистрация: 25.12.2011
Сообщений: 443
06.05.2013, 12:27 #7
Цитата Сообщение от Death99_99 Посмотреть сообщение
На плоскости заданы своими целочисленными координатами n точек. Найти всевозможные группы по 3,4... точки, лежащие на одной прямой.
Точки могут совпадать?
Цитата Сообщение от Death99_99 Посмотреть сообщение
C++
1
2
3
4
5
6
...
    arrx=new int;
    arry=new int;
...
        cin >> arrx[i] >> arry[i];
...
Память выделили под один единственный int, а затем стали по индексу обращаться.

Зачем вообще указатели и ручная работа с памятью, это же C++, нужно использовать контейнер, который сам за памятью следит, например, std::vector.
0
Death99_99
0 / 0 / 0
Регистрация: 06.05.2013
Сообщений: 18
06.05.2013, 12:32  [ТС] #8
Цитата Сообщение от Bend3r Посмотреть сообщение
У меня программа вообще не работает. Обьяснить еще раз подробно задание попытаюсь решить ваше задание.(Только подробно)
Вобщем с клавиатуры вводится количество точек и их координаты. Нужно вывести на экран всевозможные группы точек (в группе не менее 3-х точек) лежащих на одной прямой.
Пример: 8 точек
(0;0)
(5;7)
(1;1)
(6;7)
(2;5)
(10;10)
(0;7)
(9;7)
Из этих точек он выводит 2 группы:
1,3,6 точки
2,4,7,8 точки

А если таких групп нет, то выводить ничего не нужно.

Добавлено через 2 минуты
Цитата Сообщение от kamre Посмотреть сообщение
Точки могут совпадать?
Считается, что лежат на одной прямой.

Цитата Сообщение от kamre Посмотреть сообщение
Память выделили под один единственный int, а затем стали по индексу обращаться.
Зачем вообще указатели и ручная работа с памятью, это же C++, нужно использовать контейнер, который сам за памятью следит, например, std::vector.
В С++ я еще новичек и с вектором не знаком, поэтому пытаюсь сделать простыми путями.
0
Bend3r
149 / 136 / 35
Регистрация: 29.07.2012
Сообщений: 709
06.05.2013, 12:37 #9
Вообще ввожу я например точку 5 и точку 10. Программе необходимо подсчитать сколько точек может находится на прямой начало с 5 и до 10 см допустим. Так я вас понимаю?

До меня не доходит суть вашей задачи
0
Death99_99
0 / 0 / 0
Регистрация: 06.05.2013
Сообщений: 18
06.05.2013, 12:58  [ТС] #10
Цитата Сообщение от Bend3r Посмотреть сообщение
Вообще ввожу я например точку 5 и точку 10. Программе необходимо подсчитать сколько точек может находится на прямой начало с 5 и до 10 см допустим. Так я вас понимаю?

До меня не доходит суть вашей задачи
НА ПЛОСКОСТИ имеется несколько точек с координатами (х;у). Из всех точек найти только те, которые лежат на одной прямой (т.е. прямая образуется этими же точками)
0
Bend3r
149 / 136 / 35
Регистрация: 29.07.2012
Сообщений: 709
06.05.2013, 13:20 #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
#pragma hdrstop
#include <iostream>
#include <Windows>
#include <stdio.h>
#include <ctype.h>
#include <stdlib.h>
#include <conio.h>
 
using namespace std;
 
void main()
{
SetConsoleCP(1251);
SetConsoleOutputCP(1251);
 
int point,point1,k;
k=1;
cout << "Ввод первой точки - ";
cin >> point;
cout << "Ввод второй точки - ";
cin >> point1;
cout << "Точки лежащие на прямой c координатами ("<<point<<";"<<point1<<").\n";
for(int i = point; i < point1; i++)
{
if((i+1)==point1) break; cout << "Точки №"<<k<< " - " << i+1 << "\n";
k++;
}
 
system("PAUSE");
}
0
Miwa123
37 / 37 / 22
Регистрация: 16.04.2013
Сообщений: 319
Записей в блоге: 1
06.05.2013, 14:06 #12
Цитата Сообщение от Bend3r Посмотреть сообщение
Вообще ввожу я например точку 5 и точку 10. Программе необходимо подсчитать сколько точек может находится на прямой начало с 5 и до 10 см допустим. Так я вас понимаю?

До меня не доходит суть вашей задачи
видимо подробное объяснение не поможет решить Вам данную задачу...
по теме: и в правда ошибка. попытаюсь исправить в ближайшие 2 часа!

Добавлено через 27 минут
Цитата Сообщение от Miwa123 Посмотреть сообщение
видимо подробное объяснение не поможет решить Вам данную задачу...
по теме: и в правда ошибка. попытаюсь исправить в ближайшие 2 часа!
я не в силах уже... Death99 попытайся разобраться в коде. потесть циклы может я где-то опечатался...
0
kamre
127 / 131 / 11
Регистрация: 25.12.2011
Сообщений: 443
06.05.2013, 14:11 #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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <set>
#include <vector>
#include <algorithm>
#include <functional>
#include <fstream>
#include <iostream>
 
using namespace std;
using namespace std::placeholders;
 
typedef pair<int, int>         point_t;
typedef set<point_t>           points_t;
typedef pair<point_t, point_t> line_t;
typedef vector<line_t>         lines_t;
typedef vector<points_t>       groups_t;
 
bool point_on_line(const point_t & p, const line_t & l)
{
    int dx = l.second.first - l.first.first;
    int dy = l.second.second - l.first.second;
    int x0 = l.first.first;
    int y0 = l.first.second;
    return -dy*(p.first - x0) + dx*(p.second - y0) == 0;
}
 
bool same_line(const line_t & l0, const line_t & l1)
{
    // compute line directions
    int dx0 = l0.second.first - l0.first.first;
    int dx1 = l1.second.first - l1.first.first;
    int dy0 = l0.second.second - l0.first.second;
    int dy1 = l1.second.second - l1.first.second;
    // compare directions
    if (dx0*dy1 - dy0*dx1 != 0)
        return false;
    // check if first point of l0 is on l1
    return point_on_line(l0.first, l1);
}
 
int main()
{
    // read points from file
    ifstream inp("input.txt");
    int n;
    inp >> n;
    points_t pts;
    while (n--) {
        int x, y;
        inp >> x >> y;
        pts.insert(point_t(x, y));
    }
 
    // unique lines
    lines_t ls;
 
    // groups of points on the same line
    groups_t gs;
 
    // consider all pairs of points
    for (auto p0 = pts.begin(); p0 != pts.end(); ++p0) {
        for (auto p1 = p0; ++p1 != pts.end();) {
            // check if line for pair of points was already considered
            line_t l(*p0, *p1);
            auto it = find_if(ls.begin(), ls.end(), bind(same_line, l, _1));
            if (it != ls.end())
                continue;
            ls.push_back(l);
            // compute all points on the line
            points_t g = { *p0, *p1 };
            for (auto p2 = p1; ++p2 != pts.end();) {
                if (point_on_line(*p2, l))
                    g.insert(*p2);
            }
            if (g.size() > 2)
                gs.push_back(g);
        }
    }
 
    // print groups of points
    for (size_t i = 0; i < gs.size(); ++i) {
        cout << i << ":";
        for (auto p : gs[i]) {
            cout << " (" << p.first << "," << p.second << ")";
        }
        cout << endl;
    }
}
Цитата Сообщение от input.txt
8
0 0
5 7
1 1
6 7
2 5
10 10
0 7
9 7
Цитата Сообщение от stdout
0: (0,0) (1,1) (10,10)
1: (0,7) (5,7) (6,7) (9,7)
1
Death99_99
0 / 0 / 0
Регистрация: 06.05.2013
Сообщений: 18
27.05.2013, 20:26  [ТС] #14
Нашел ошибку в программе и доработал.
Кликните здесь для просмотра всего текста
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;
bool uravnenie(double x1,double y1,double x2,double y2,double &K,double &B);
int main()
{
    double k,*arrx,*arry,K,B;
    setlocale(LC_ALL,"Russian");
    cout << "Введите Количество точек, лежащих в координатной плоскости:" << '\n';
    cin >> k;
    arrx=new double[int(k)];
    arry=new double[int(k)];
    cout << "Вводите координаты точек по порядку:" << '\n';
    for (int i=0; i<k; i++)
    {
        cin >> arrx[i] >> arry[i];
        cout << '\n';
    }
 
 
    for(int i=0;i<k;i++)
    {
 
        for(int j=i+1;j<k;j++)
        { 
            uravnenie(arrx[i],arry[i],arrx[j],arry[j],K,B);
            for(int m=0;m<k;m++)
            {
                if(m==i || m==j) continue;
                if(arry[m]==K*arrx[m]+B)
                {
                    cout << "на прямой, которая проведена через точками с нормерами " << i+1 << " - " << j+1 << " лежит точка " << m+1 << '\n';
                }
                
            }
        }
 
 
    }
 
    delete arrx;
    delete arry;
    system ("pause");
    return 0;
}
 
bool uravnenie(double x1,double y1,double x2,double y2,double &K,double &B)
{
 
 
 
    if((y1-y2)==0 || (x1-x2)==0)
        K=0;
    else
        K=(y1-y2)/(x1-x2);
    B=y1-K*x1;
     
    
 
    return true;
}

Все работает, но остался еще один маленький недочет: Не выводит, если прямая горизонтальная. Последняя программа на форуме не подходит, так как мне нужно еще эту программу объяснить, а я не совсем разбираюсь еще в с++. Прошу помочь с готовой программой.
0
Death99_99
0 / 0 / 0
Регистрация: 06.05.2013
Сообщений: 18
29.05.2013, 19:57  [ТС] #15
Блин, помогите пожалуйста
0
Death99_99
0 / 0 / 0
Регистрация: 06.05.2013
Сообщений: 18
13.06.2013, 23:33  [ТС] #16
Цитата Сообщение от kamre Посмотреть сообщение
Вот такой вариант:
Кликните здесь для просмотра всего текста
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
78
79
80
81
82
83
84
85
86
87
#include <set>
#include <vector>
#include <algorithm>
#include <functional>
#include <fstream>
#include <iostream>
 
using namespace std;
using namespace std::placeholders;
 
typedef pair<int, int>         point_t;
typedef set<point_t>           points_t;
typedef pair<point_t, point_t> line_t;
typedef vector<line_t>         lines_t;
typedef vector<points_t>       groups_t;
 
bool point_on_line(const point_t & p, const line_t & l)
{
    int dx = l.second.first - l.first.first;
    int dy = l.second.second - l.first.second;
    int x0 = l.first.first;
    int y0 = l.first.second;
    return -dy*(p.first - x0) + dx*(p.second - y0) == 0;
}
 
bool same_line(const line_t & l0, const line_t & l1)
{
    // compute line directions
    int dx0 = l0.second.first - l0.first.first;
    int dx1 = l1.second.first - l1.first.first;
    int dy0 = l0.second.second - l0.first.second;
    int dy1 = l1.second.second - l1.first.second;
    // compare directions
    if (dx0*dy1 - dy0*dx1 != 0)
        return false;
    // check if first point of l0 is on l1
    return point_on_line(l0.first, l1);
}
 
int main()
{
    // read points from file
    ifstream inp("input.txt");
    int n;
    inp >> n;
    points_t pts;
    while (n--) {
        int x, y;
        inp >> x >> y;
        pts.insert(point_t(x, y));
    }
 
    // unique lines
    lines_t ls;
 
    // groups of points on the same line
    groups_t gs;
 
    // consider all pairs of points
    for (auto p0 = pts.begin(); p0 != pts.end(); ++p0) {
        for (auto p1 = p0; ++p1 != pts.end();) {
            // check if line for pair of points was already considered
            line_t l(*p0, *p1);
            auto it = find_if(ls.begin(), ls.end(), bind(same_line, l, _1));
            if (it != ls.end())
                continue;
            ls.push_back(l);
            // compute all points on the line
            points_t g = { *p0, *p1 };
            for (auto p2 = p1; ++p2 != pts.end();) {
                if (point_on_line(*p2, l))
                    g.insert(*p2);
            }
            if (g.size() > 2)
                gs.push_back(g);
        }
    }
 
    // print groups of points
    for (size_t i = 0; i < gs.size(); ++i) {
        cout << i << ":";
        for (auto p : gs[i]) {
            cout << " (" << p.first << "," << p.second << ")";
        }
        cout << endl;
    }
}
На чем писал? В Visual Studio выдает не мало ошибок. Консольное это?
0
kamre
127 / 131 / 11
Регистрация: 25.12.2011
Сообщений: 443
15.06.2013, 21:17 #17
Цитата Сообщение от Death99_99 Посмотреть сообщение
На чем писал?
На C++11.

Цитата Сообщение от Death99_99 Посмотреть сообщение
В Visual Studio выдает не мало ошибок.
Собирал и тестировал на gcc 4.7.2 в mingw варианте. Надо по новее студию взять, 2012 версию. Или переписать те места, где ругается на фичи из C++11, которые не поддерживаются.

Цитата Сообщение от Death99_99 Посмотреть сообщение
Консольное это?
Программа обычная консольная.
0
15.06.2013, 21:17
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
15.06.2013, 21:17
Привет! Вот еще темы с решениями:

Определите, лежат ли точки на одной прямой
1)Заданы три точки на плоскости: М с координатами(x1,y1), L с...

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

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

Из одной точки к прямой проведены перпендикуляр и наклонная
Из одной точки к прямой проведены перпендикуляр и наклонная. По длинам отрезков...


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

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

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