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

Программа нахождении минимально удалённой точки от других точек - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.89
nicenice
3 / 3 / 0
Регистрация: 22.11.2011
Сообщений: 168
03.01.2012, 11:07     Программа нахождении минимально удалённой точки от других точек #1
Есть идеи как это можно сделать?

те ты вводиш кооординаты двух или нескольких точек, программа должна найти минимальное расстояние от каждой точки до других и вывести эту минимальную удалённую точку

программа должна быть со структурой х и y и функцией считающей расстояние
структуру и функцию я создал, осталось самое главное нахождение точки
а расстояние я находил по формуле sqrt((x2-x1)^2+(y2-y1)^2)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.01.2012, 11:07     Программа нахождении минимально удалённой точки от других точек
Посмотрите здесь:

C++ Возможное округление при нахождении 2-й производной. При повышении точности программа начинает возвращать 0.
C++ Ошибка в нахождении точек пересечения
C++ найти точку, у которой сумма расстояний до других точек наименьшая?
Точки пересечения прямой и функции с множеством точек C++
C++ не получается задачка (Дана точка A и множество B из N точек. Найти номер точки из множества B, наиболее удаленной от точки A)
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
soon
 Аватар для soon
2536 / 1301 / 81
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
03.01.2012, 13:12     Программа нахождении минимально удалённой точки от других точек #2
Сложить расстояния от точки до всех остальных и найти наименьшее.
nicenice
3 / 3 / 0
Регистрация: 22.11.2011
Сообщений: 168
03.01.2012, 21:38  [ТС]     Программа нахождении минимально удалённой точки от других точек #3
Это легко написать словами, код написать намного сложнее, по крайней мере для меня.
Вот начал, не знаю как дальше быть.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<math.h>
#include<stdio.h>
#include<conio.h>
struct tchk
{
    int x, y;
};
float rast(tchk a, tchk b)
{
    float x, y, d;
    x = b.x - a.x;
    y = b.y - a.y;
    d = sqrt(x*x + y*y);
    return d;
}
int main()
{
soon
 Аватар для soon
2536 / 1301 / 81
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
03.01.2012, 22:43     Программа нахождении минимально удалённой точки от других точек #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
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>
#include <cmath>
#include <vector>
#include <algorithm>
 
template <class T> T sqr(T a) { return a * a; }
 
class Point 
{
    float x;
    float y;
    
public:
    Point(): x(0), y(0)
    {
        
    }
    
    friend std::istream& operator >> (std::istream& stream, Point& p)
    {
        stream >> p.x;
        stream >> p.y;
        return stream;
    }
    
    friend std::ostream& operator << (std::ostream& stream, const Point& p)
    {
        stream << '(' << p.x << "; " << p.y << ')';
        return stream;
    }
    
    friend float distanceTo(Point p1, Point p2)
    {
        return sqrt(sqr(p1.x - p2.x) + sqr(p1.y - p2.y));
    }
};
 
int main()
{
    typedef std::vector<Point> VecPoint;
    typedef VecPoint::iterator VecPointItr;
    typedef std::vector<float> VecFloat;
    const int size = 10;
    std::vector<Point> points(size);
    for(VecPointItr it = points.begin(); it != points.end(); ++it)
        std::cin >> *it;
    VecFloat d;
    for(int i = 0; i < size; ++i)
    {
        float sum = 0;
        for(int j = 0; j < i; ++j)
            sum += distanceTo(points.at(i), points.at(j));
        for(int j = i + 1; j < size; ++j)
            sum += distanceTo(points.at(i), points.at(j));
        d.push_back(sum);
    }
    int pos = std::min_element(d.begin(), d.end()) - d.begin();
    std::cout << "min #" << pos << ", = " << points.at(pos) << std::endl;
    return 0;
}
lemegeton
 Аватар для lemegeton
2910 / 1339 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
03.01.2012, 22:57     Программа нахождении минимально удалённой точки от других точек #5
Чет я многабукаф использовал.
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 <cmath>
#include <ctime>
#include <cstdlib>
#include <iostream>
 
class Point {
 public:
  Point() : x_(0.), y_(0.) {}
  Point(float x, float y) : x_(x), y_(y) {}
  float getX() const { return x_; }
  float getY() const { return y_; }
  float getDistanceTo(const Point &point) const {
    return sqrt(pow(point.getX() - getX(), 2.) +
      pow(point.getY() - getY(), 2.));
  }
  static Point randomPoint() {
    return Point((rand() % 1000) / 100., (rand() % 1000) / 100.);
  }
 private:
  float x_, y_;
};
 
std::ostream &operator<<(std::ostream &stream, const Point &point) {
  return stream << "[" << point.getX() << ":" << point.getY() << "]";
}
 
float sumOfDistances(size_t id, const Point *points, size_t size) {
  float sum = 0.;
  for (size_t i = 0; i < size; ++i)
    if (i != id)
      sum += points[id].getDistanceTo(points[i]);
  return sum;
}
 
int main(int argc, char *argv[]) {
  srand(time(0));
  size_t numberOfPoints = 10;
  Point *points = new Point[numberOfPoints]();
 
  std::cout << "Points: ";
  for (size_t i = 1; i < numberOfPoints; ++i)
    std::cout << (points[i] = Point::randomPoint()) << " ";
  std::cout << std::endl;
 
  size_t minPointId = 0;
  float minPointDistanceSum = sumOfDistances(minPointId, points, numberOfPoints);
  for (size_t i = 1; i < numberOfPoints; ++i) {
    float currentPointDistanceSum = sumOfDistances(i, points, numberOfPoints);
    if (currentPointDistanceSum < minPointDistanceSum) {
      minPointDistanceSum = currentPointDistanceSum;
      minPointId = i;
    }
  }
 
  std::cout << "Closest point: " << points[minPointId] << std::endl <<
    "Sum of distances: " << minPointDistanceSum << std::endl;
  
  delete [] points;
  return 0;
}
nicenice
3 / 3 / 0
Регистрация: 22.11.2011
Сообщений: 168
04.01.2012, 10:06  [ТС]     Программа нахождении минимально удалённой точки от других точек #6
soon, lemegeton, спасибо. Это у вас на С++ написано? Что-то для меня большая часть абра-кадабра... наверное я изучаю язык Си без ++
soon
 Аватар для soon
2536 / 1301 / 81
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
04.01.2012, 10:29     Программа нахождении минимально удалённой точки от других точек #7
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
#include <stdio.h>
#include <math.h>
 
float sqr(float a) { return a * a; }
 
typedef struct
{
    float x;
    float y;
} Point;
 
float distance(Point p1, Point p2)
{
    return sqrt(sqr(p1.x - p2.x) + sqr(p1.y - p2.y));
}
 
float* min_element(float* first, float* last)
{
    float* min = first;
    for(++first; first != last; ++first)
        if(*first < *min)
            min = first;
    return min;
}
 
int main(void)
{
    int size = 10;
    Point points[size];
    float d[size];
    int i, j;
    for(i = 0; i < size; ++i)
        scanf("%f%f", &points[i].x, &points[i].y);
    for(i = 0; i < size; ++i)
    {
        float sum = 0;
        for(j = 0; j < i; ++j)
            sum += distance(points[i], points[j]);
        for(j = i + 1; j < size; ++j)
            sum += distance(points[i], points[j]);
        d[i] = sum;
    }
    int pos = min_element(d, d + size) - d;
    printf("min #%d, = (%f; %f)\n", pos, points[pos].x, points[pos].y);
    return 0;
}
nicenice
3 / 3 / 0
Регистрация: 22.11.2011
Сообщений: 168
05.01.2012, 21:04  [ТС]     Программа нахождении минимально удалённой точки от других точек #8
soon, спасибо.

А как можно сделать так чтобы если бы таких точек было несколько, прога их всех бы выводила?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.01.2012, 21:07     Программа нахождении минимально удалённой точки от других точек
Еще ссылки по теме:

C++ Найти координаты точки наиболее удалённой от начала координат. Если таких точек несколько, вывести первую найденную
Функция, которая вернет номера двух из трех заданных точек на плоскости, расстояние между которыми минимально C++
Ввести координаты точек. Вычислить расстояния от всех точек до точки, введенной последней C++

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

Или воспользуйтесь поиском по форуму:
soon
 Аватар для soon
2536 / 1301 / 81
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
05.01.2012, 21:07     Программа нахождении минимально удалённой точки от других точек #9
Цитата Сообщение от nicenice Посмотреть сообщение
А как можно сделать так чтобы если бы таких точек было несколько, прога их всех бы выводила?
После нахождения минимального элемента пройдите по массиву, узнайте номера всех элементов с такой же суммой и выведите их.
Yandex
Объявления
05.01.2012, 21:07     Программа нахождении минимально удалённой точки от других точек
Ответ Создать тему
Опции темы

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