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

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

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

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

06.05.2013, 08:37. Просмотров 1115. Ответов 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;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
06.05.2013, 08:37     Найти всевозможные группы по 3,4. точки, лежащие на одной прямой
Посмотрите здесь:
C++ Определить минимальное подмножество точек, после удаления которых останутся точки лежащие на одной прямой
C++ Выбрать такие три точки из множества, не лежащие на одной прямой, которые составляют треугольник min площади
C++ Определить, лежат ли три точки A, B, C на одной прямой. Если нет, найти угол ABC
Принадлежат ли точки одной прямой C++
Определить, лежат ли точки на одной прямой C++
C++ Определить расположены ли точки на одной прямой
C++ Определите, лежат ли точки на одной прямой
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Miwa123
37 / 37 / 1
Регистрация: 16.04.2013
Сообщений: 317
Записей в блоге: 1
06.05.2013, 11:37     Найти всевозможные группы по 3,4. точки, лежащие на одной прямой #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;
}
Death99_99
0 / 0 / 0
Регистрация: 06.05.2013
Сообщений: 18
06.05.2013, 11:50  [ТС]     Найти всевозможные группы по 3,4. точки, лежащие на одной прямой #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;
}
Появляется вот такая ошибка.
Миниатюры
Найти всевозможные группы по 3,4. точки, лежащие на одной прямой  
Bend3r
149 / 136 / 18
Регистрация: 29.07.2012
Сообщений: 709
06.05.2013, 12:01     Найти всевозможные группы по 3,4. точки, лежащие на одной прямой #4
Цитата Сообщение от Death99_99 Посмотреть сообщение
Появляется вот такая ошибка.
Скорей всего ты где-то сделал точку остановы. Просто перезапусти студию.
Death99_99
0 / 0 / 0
Регистрация: 06.05.2013
Сообщений: 18
06.05.2013, 12:14  [ТС]     Найти всевозможные группы по 3,4. точки, лежащие на одной прямой #5
Цитата Сообщение от Bend3r Посмотреть сообщение
Скорей всего ты где-то сделал точку остановы. Просто перезапусти студию.
Не помогло. Заметил такую особенность. Такая ошибка вылетает если количество точек более 5 и есть хотя бы 3 точки лежащие на одной прямой.
До 5 точек все прекрасно работает.
Bend3r
149 / 136 / 18
Регистрация: 29.07.2012
Сообщений: 709
06.05.2013, 12:21     Найти всевозможные группы по 3,4. точки, лежащие на одной прямой #6
У меня программа вообще не работает. Обьяснить еще раз подробно задание попытаюсь решить ваше задание.(Только подробно)
kamre
126 / 130 / 4
Регистрация: 25.12.2011
Сообщений: 443
06.05.2013, 12:27     Найти всевозможные группы по 3,4. точки, лежащие на одной прямой #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.
Death99_99
0 / 0 / 0
Регистрация: 06.05.2013
Сообщений: 18
06.05.2013, 12:32  [ТС]     Найти всевозможные группы по 3,4. точки, лежащие на одной прямой #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.
В С++ я еще новичек и с вектором не знаком, поэтому пытаюсь сделать простыми путями.
Bend3r
149 / 136 / 18
Регистрация: 29.07.2012
Сообщений: 709
06.05.2013, 12:37     Найти всевозможные группы по 3,4. точки, лежащие на одной прямой #9
Вообще ввожу я например точку 5 и точку 10. Программе необходимо подсчитать сколько точек может находится на прямой начало с 5 и до 10 см допустим. Так я вас понимаю?

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

До меня не доходит суть вашей задачи
НА ПЛОСКОСТИ имеется несколько точек с координатами (х;у). Из всех точек найти только те, которые лежат на одной прямой (т.е. прямая образуется этими же точками)
Bend3r
149 / 136 / 18
Регистрация: 29.07.2012
Сообщений: 709
06.05.2013, 13:20     Найти всевозможные группы по 3,4. точки, лежащие на одной прямой #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");
}
Miwa123
37 / 37 / 1
Регистрация: 16.04.2013
Сообщений: 317
Записей в блоге: 1
06.05.2013, 14:06     Найти всевозможные группы по 3,4. точки, лежащие на одной прямой #12
Цитата Сообщение от Bend3r Посмотреть сообщение
Вообще ввожу я например точку 5 и точку 10. Программе необходимо подсчитать сколько точек может находится на прямой начало с 5 и до 10 см допустим. Так я вас понимаю?

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

Добавлено через 27 минут
Цитата Сообщение от Miwa123 Посмотреть сообщение
видимо подробное объяснение не поможет решить Вам данную задачу...
по теме: и в правда ошибка. попытаюсь исправить в ближайшие 2 часа!
я не в силах уже... Death99 попытайся разобраться в коде. потесть циклы может я где-то опечатался...
kamre
126 / 130 / 4
Регистрация: 25.12.2011
Сообщений: 443
06.05.2013, 14:11     Найти всевозможные группы по 3,4. точки, лежащие на одной прямой #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)
Death99_99
0 / 0 / 0
Регистрация: 06.05.2013
Сообщений: 18
27.05.2013, 20:26  [ТС]     Найти всевозможные группы по 3,4. точки, лежащие на одной прямой #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;
}

Все работает, но остался еще один маленький недочет: Не выводит, если прямая горизонтальная. Последняя программа на форуме не подходит, так как мне нужно еще эту программу объяснить, а я не совсем разбираюсь еще в с++. Прошу помочь с готовой программой.
Death99_99
0 / 0 / 0
Регистрация: 06.05.2013
Сообщений: 18
29.05.2013, 19:57  [ТС]     Найти всевозможные группы по 3,4. точки, лежащие на одной прямой #15
Блин, помогите пожалуйста
Death99_99
0 / 0 / 0
Регистрация: 06.05.2013
Сообщений: 18
13.06.2013, 23:33  [ТС]     Найти всевозможные группы по 3,4. точки, лежащие на одной прямой #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 выдает не мало ошибок. Консольное это?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
15.06.2013, 21:17     Найти всевозможные группы по 3,4. точки, лежащие на одной прямой
Еще ссылки по теме:
Из одной точки к прямой проведены перпендикуляр и наклонная C++
Лежат ли точки на одной прямой и вычислить угол C++
Определить, будут ли точки расположены на одной прямой C++
Определить лежат ли три точки на одной прямой C++
Определить будут ли заданные три точки расположены на одной прямой C++

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

Или воспользуйтесь поиском по форуму:
kamre
126 / 130 / 4
Регистрация: 25.12.2011
Сообщений: 443
15.06.2013, 21:17     Найти всевозможные группы по 3,4. точки, лежащие на одной прямой #17
Цитата Сообщение от Death99_99 Посмотреть сообщение
На чем писал?
На C++11.

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

Цитата Сообщение от Death99_99 Посмотреть сообщение
Консольное это?
Программа обычная консольная.
Yandex
Объявления
15.06.2013, 21:17     Найти всевозможные группы по 3,4. точки, лежащие на одной прямой
Ответ Создать тему
Опции темы

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