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

Поиск точек на плоскости - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 10, средняя оценка - 4.60
Trisha Ray
80 / 0 / 0
Регистрация: 01.02.2012
Сообщений: 93
03.03.2013, 16:10     Поиск точек на плоскости #1
разработать объектно-ориентированную прогу для поиска пары наиболее близких точек из любого заданного набора точек на плоскости. Декартовые координаты всех его точек должны быть специфицированы парами целых чисел в аргументах командной строки вызова проги. Координаты полученной пары ближайших точек набора и расстояние между ними должны отображаться строкой потока стандартного вывода. В проге должен быть реализован класс точки с приватными полями для ее декартовых координат, публичными методами доступа к ним и конструктором инициализации их значений, а так же метод для вычисления расстояния до любой другой заданной точки. Кроме того, в проге должно быть предусмотрено динамическое распределение памяти для всех точек заданного набора и массива их адресов

Помогите, пожалуйста!!!
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Tulosba
:)
Эксперт С++
4378 / 3221 / 297
Регистрация: 19.02.2013
Сообщений: 9,044
04.03.2013, 16:12     Поиск точек на плоскости #2
Цитата Сообщение от Trisha Ray Посмотреть сообщение
Помогите, пожалуйста!!!
В чем конкретно у Вас загвоздка?
Trisha Ray
80 / 0 / 0
Регистрация: 01.02.2012
Сообщений: 93
04.03.2013, 19:07  [ТС]     Поиск точек на плоскости #3
у меня есть класс точка с private x и y и public getx() gety() и метод double distance (point *q) {double d=sqrt((x-q->x)^2+(y-q->y)^2); return d;}. В main описан point **p где p=new point*[argc] и заполняемый в цикле. Как связать перебор чисел и метод вычисления?? И как сделать перебор??
Tulosba
:)
Эксперт С++
4378 / 3221 / 297
Регистрация: 19.02.2013
Сообщений: 9,044
04.03.2013, 19:29     Поиск точек на плоскости #4
Набросал такой код:
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
#include <iostream>
#include <cmath>
#include <vector>
 
class point
{
public:
    point( int x, int y ) : x(x), y(y) {}
    int getx() const { return x; }
    int gety() const { return y; }
    double distance (point *q) {
        return sqrt( (double)( (x-q->x)*(x-q->x) + (y-q->y)*(y-q->y) ) ); 
    }
private: 
    const int x;
    const int y;
};
 
int main( int argc, char* argv[] )
{
    int cnt = (argc - 1) / 2; // Кол-во точек
    
    std::vector<point> points; // Вектор для точек
 
    for( int i=0; i<cnt; ++i ) // Перебор 
    {
        int x = strtol( argv[i*2 + 1], 0, 10 );
        int y = strtol( argv[i*2 + 2], 0, 10 );
 
        points.push_back( point( x, y ) ); // Заполнение вектора
 
        std::cout << i << " = " << points[i].getx() << ":" << points[i].gety() << std::endl;
    }
    system("PAUSE");
}
Что не ясно, спрашивайте.

P.S. Оператор ^ в С/С++ не является оператором возведения в степень (это Вам не бейсик).
Для возведения в степень следует использовать функцию pow();
booker
 Аватар для booker
23 / 23 / 2
Регистрация: 21.11.2012
Сообщений: 106
04.03.2013, 20:35     Поиск точек на плоскости #5
функция

C++ (Qt)
1
2
3
 double distance (point *q) {
        return sqrt( (double)( (x-q->x)*(x-q->x) + (y-q->y)*(y-q->y) ) ); 
    }
должна быть во friend функции класса point, вычитающей дистанцию между точками, объектами point

Добавлено через 7 минут
у класса поинт неплохо бы прегрузить оператор []

Добавлено через 29 минут
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
#include <iostream>
#include <cmath>
#include <vector>
 
class point
{
public:
    point( int x, int y ) : x(x), y(y) {}
    int getx() const { return x; }
    int gety() const { return y; }
    double distance (point *q) {
        return sqrt( (double)( (x-q->x)*(x-q->x) + (y-q->y)*(y-q->y) ) ); 
    };
    
private: 
    const int x;
    const int y;
};
 
int main(  )
{
    point one(0,0);
    point two(3,4);
 
    std::cout<<one.distance(&two);
        
    system("PAUSE");
}
хотя я проверил программа рабочая у вас наверно какие то непонятки с командной строкой

Добавлено через 7 минут
и да вам еще сортировку вектора надо сделать, чтоб выяснить наиболее близкую дистанцию

всмысле не сортировку а пробежаться по вектору и найти минимальное значение функции distance
Tulosba
:)
Эксперт С++
4378 / 3221 / 297
Регистрация: 19.02.2013
Сообщений: 9,044
04.03.2013, 20:40     Поиск точек на плоскости #6
Цитата Сообщение от booker Посмотреть сообщение
должна быть во friend функции класса point
Вы имеете какое-то отношение к ТС или чем объясняется Ваше замечание?
Цитата Сообщение от booker Посмотреть сообщение
у класса поинт неплохо бы прегрузить оператор []
Для каких целей?
tur9
43 / 4 / 1
Регистрация: 20.08.2012
Сообщений: 84
04.03.2013, 20:57     Поиск точек на плоскости #7
У меня похожая задача. (но не про классы, программирование, а про алгоритм)
Есть N точек на плоскости.
Надо найти все группы точек, находящиеся друг от друга на расстоянии R или меньше.
Как это сделать оптимально?
Допустим так:
Создаем массив bol в N членов для отметки использованных точек и заполняем его нулями.

1. Берем первую точку (из массива точек) и ищем среди оставшихся точек те, которые по Х не отличаются более чем на +/- R. Находим например К точек.
2. Среди этих К точек ищем те, которые по Y не отличаются более чем на +/- R от первой точки. Допустим нашли Р таких точек.
3. Среди Р точек ищем те, которые внутри радиуса R от первой точки. Допустим нашли М таких точек.

После нахождения этих М точек имеем также их индексы из исходного массива N точек. В соответствующих индексах помечаем в массиве bol что эти точки уже использованы (ставим туда напр 1) и не подлежат дальнейшим вычислениям.

Ищем следующую свободную точку в массиве N при учете, что на соответствующем месте в bol есть ноль.
Повторяем процесс с учетом того что не следует брать точки для которых в bol уже 1

На сколько оптимален по времени этот алгоритм? Может есть лучший?
booker
 Аватар для booker
23 / 23 / 2
Регистрация: 21.11.2012
Сообщений: 106
04.03.2013, 22:05     Поиск точек на плоскости #8
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 <iostream>
#include <math.h>
#include <vector>
#include<time.h>
 
 
class point
{
public:
    point():x(0),y(0){};
    point( int x, int y ) : x(x), y(y) {}
    int getx() const { return x; }
    int gety() const { return y; }
    double distance (point *q) {
        return sqrt( (double)( (x-q->x)*(x-q->x) + (y-q->y)*(y-q->y) ) ); 
    };
    //почему бы и нет
    friend double distance (point *one,point *two){
    return sqrt( (double)( pow((double)(one->x-two->x),2) + pow((double)(one->y-two->y),2)) );
    };
 
 
private: 
    const int x;
    const int y;
};
 
int main(  )
{
    point one(0,0);
    point two(3,4);
 
    std::cout<<distance(&one,&two)<<std::endl; // ведь такой синтаксис может быть удобен 
        
    srand(static_cast<unsigned>(time(NULL)));
            
    std::vector<point>points;
 
    for(int n=0;n<100;n++){
 
        points.push_back(point(rand()%100,rand()%100));
    }
 
 
    std::vector<point>::iterator iter1=points.begin();
    std::vector<point>::iterator iter2=points.begin()+1;
 
    double min= distance(iter1,iter2);
    double max= distance(iter1,iter2);
 
    for (iter1=points.begin();iter1!=points.end();iter1++)
    {
        for (iter2=iter1+1;iter2!=points.end();iter2++){
            if(distance(iter1,iter2)<min)min=distance(iter1,iter2);
                    if(distance(iter1,iter2)>max)max=distance(iter1,iter2);
        }
    }
        
    std::cout<<min<<" "<<max;
            
    system("PAUSE");
}
Добавлено через 1 минуту
вывод смущает, наверное опять в чём то не прав(
Trisha Ray
80 / 0 / 0
Регистрация: 01.02.2012
Сообщений: 93
04.03.2013, 23:12  [ТС]     Поиск точек на плоскости #9
Tulosba Если вам не сложно, не могли бы объяснить что делает strtol, std::vector<point> points; // Вектор для точек - как он работает? и push_back.
Tulosba
:)
Эксперт С++
4378 / 3221 / 297
Регистрация: 19.02.2013
Сообщений: 9,044
05.03.2013, 00:06     Поиск точек на плоскости #10
strtol
vector
I.M.
 Аватар для I.M.
564 / 547 / 5
Регистрация: 16.12.2011
Сообщений: 1,389
05.03.2013, 00:19     Поиск точек на плоскости #11
booker, в вашем коде вызывается distance(iterator, iterator) - это стандартная функция, которая не имеет отношения к высчитыванию расстояния между точками.
Сам метод distance просто должен быть внешним - зачем городить дружеские функции?
сигнатура должна быть примерно следующая:
double distance(const point& i_left, const point& i_right);
Trisha Ray
80 / 0 / 0
Регистрация: 01.02.2012
Сообщений: 93
06.03.2013, 00:16  [ТС]     Поиск точек на плоскости #12
Сказали что надо делать по другому через обращения к методу и тп.

Вот код: не знаю как обратиться к методу в классе из функции main. Как думаете - правильно работать будет?

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 <math.h>
#define MIN 1000000
 
class point
{
private: int x; int y; 
public: 
point(int _x,int _y):x(_x),y(_y){};
int getx(){return x;} int gety(){return y;}
double distance(point *q)
{double d=((x-q->x)*(x-q->x)-(y-q->y)*(y-q->y));
 return (sqrt(d));}
};
 
int main(int argc,char *argv[])
{
int x,y;
point **p;
int i=0,j=0,k=0;
if(argc<2)
return(-1);
p=new point* [argc];
while(++i<argc)
{
sscanf(argv[i],"(%d%*c%d)",&x,&y);
p[j]=new point(x,y);
j++;
}
p[j]=NULL;
 
double mind=MIN;
double nd;
int mini,minj;
 
/*for(i=0;i<3;i++)
{for(k=0;k<3;k++)
if(i!=k)
{
//nd=p[i].distance(p[k]); - выражение слева от ".distance" должно представлять класс, структуру или объединение 
    //nd=distance(p[k]);  - идентификатор не определен
if(nd<mind)
{
mind=nd;
mini=i;
minj=k;
}
}
 
printf("Dcp(%d%d)=%f\n",p[mini],p[minj],nd);
}*/
 
/*for(i=0;p[i]!=NULL;i++)
{
    nd=0.0;
    for(j=1;p[j]!=NULL;j++)
    point.distance(p[j]); - как обратиться к методу в классе??
}*/
 
for(j=0;p[j]!=NULL;j++)
delete p[j];
delete []p;
return 0;
}
Tulosba
:)
Эксперт С++
4378 / 3221 / 297
Регистрация: 19.02.2013
Сообщений: 9,044
06.03.2013, 10:21     Поиск точек на плоскости #13
Цитата Сообщение от Trisha Ray Посмотреть сообщение
не знаю как обратиться к методу в классе из функции main.
Создаете 2 объекта класса point:
C++
1
2
point p1(10,20);
point p2(30,40);
Вычисляете расстояние от одной точки до другой (можно проверить, что dist1 == dist2):
C++
1
2
double dist1 = p1.distance(&p2);
double dist2 = p2.distance(&p1);
Ваш код не помешало бы оформить должным образом (используя теги форматирования).
А вообще, мне не понятно зачем смешивать C++ (классы, методы и пр.) с голым С (#define, printf, scanf ...)
Trisha Ray
80 / 0 / 0
Регистрация: 01.02.2012
Сообщений: 93
06.03.2013, 20:39  [ТС]     Поиск точек на плоскости #14
Про смешивание - так дали задание и пример.

А как я создам два объекта класса если для них нужно задавать значения, а по заданию нужно их вводить с консоли?
Tulosba
:)
Эксперт С++
4378 / 3221 / 297
Регистрация: 19.02.2013
Сообщений: 9,044
06.03.2013, 21:46     Поиск точек на плоскости #15
Цитата Сообщение от Trisha Ray Посмотреть сообщение
Про смешивание - так дали задание и пример.
Поубивать таких преподавателей надо.
Цитата Сообщение от Trisha Ray Посмотреть сообщение
А как я создам два объекта класса если для них нужно задавать значения, а по заданию нужно их вводить с консоли?
Легко. Хотя бы даже так (хоть это и не лучший вариант):
C++
1
2
3
4
5
6
int x1=strtol(argv[1], 0, 10);
int y1=strtol(argv[2], 0, 10);
int x2=strtol(argv[3], 0, 10);
int y2=strtol(argv[4], 0, 10);
point p1(x1,y1);
point p2(x2,y2);
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.03.2013, 10:40     Поиск точек на плоскости
Еще ссылки по теме:

C++ Список координат точек плоскости
Построить множество треугольников с вершинами в заданных точках согласно условию C++

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

Или воспользуйтесь поиском по форуму:
Trisha Ray
80 / 0 / 0
Регистрация: 01.02.2012
Сообщений: 93
07.03.2013, 10:40  [ТС]     Поиск точек на плоскости #16
спасибо)
Yandex
Объявления
07.03.2013, 10:40     Поиск точек на плоскости
Ответ Создать тему
Опции темы

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