Форум программистов, компьютерный форум, киберфорум
C++
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.60/5: Рейтинг темы: голосов - 5, средняя оценка - 4.60
0 / 0 / 0
Регистрация: 15.10.2020
Сообщений: 11

Найти разбиение множества точек на два непустых

22.03.2022, 12:26. Показов 1019. Ответов 2
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
В трёхмерном пространстве задано множество точек.Найти разбиение этого множества на два непустых непересекающихся множества,чтобы их центры тяжести находилось как можно ближе друг к другу?
0
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
22.03.2022, 12:26
Ответы с готовыми решениями:

Найти разбиение множество на два непустых непересекающихся, чтобы их центры тяжести находились как можно ближе
Здравствуйте! Есть вот такое задание: В трехмерном пространстве задано множество точек. Найти разбиение этого множество на два непустых...

Даны два множества точек на плоскости. Найти центр и радиус окружности
Даны два множества точек на плоскости. Найти центр и радиус окружности, проходящей через K (K >=3) точек первого множества и содержащий...

Даны два множества точек на плоскости. Из первого множества выбрать три точки
Даны два множества точек на плоскости .Выбрать три точки так,чтобы треугольник с вершинами содержал строго внутри себя равное количество...

2
Диссидент
Эксперт C
 Аватар для Байт
27714 / 17332 / 3810
Регистрация: 24.12.2010
Сообщений: 38,978
22.03.2022, 16:24
Тупой перебор (брут форс) - это 2n вариантов.
А сколько точек (n) может быть?
Если n больше, скажем, 10, брут форсу тут делать нечего.
Что-то вроде "ветвей и границ"?
А откуда взялась задача? Каких-то дополнительных условий нет?
0
 Аватар для igorrr37
2895 / 2042 / 992
Регистрация: 21.12.2010
Сообщений: 3,791
Записей в блоге: 9
22.03.2022, 22:58
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
88
89
90
#include <algorithm>
#include <iostream>
#include <vector>
#include <cstdlib>
#include <cmath>
#include <climits>
 
struct point
{
    double x{}, y{}, z{};
    friend bool operator==(point const& a, point const& b)
    {
        return (a.x == b.x) && (a.y == b.y) && (a.z == b.z);
    }
    friend std::ostream& operator<<(std::ostream& ost, point const& pt)
    {
        ost << "(" << pt.x << " " << pt.y << " " << pt.z << ")";
        return ost;
    }
};
 
// центр масс двух точек
point cm(point const& a, point const& b)
{
    return { a.x + (b.x - a.x) / 2.,  a.y + (b.y - a.y) / 2., a.z + (b.z - a.z) / 2. };
}
 
double dmin = DBL_MAX;
 
std::vector<std::vector<point>::const_iterator> vit, vres;
 
void calc(int rd, std::vector<point> const& ust, std::vector<point>::const_iterator ib)
{
    if (rd == 0)
    {
        point cm1{ *vit[0] };
        for (int i = 1; i < vit.size(); ++i)
        {
            cm1 = cm(cm1, *vit[i]);
        }
        auto it = std::find_if(ust.begin(), ust.end(), [](auto pt) 
            {
                return std::none_of(vit.begin(), vit.end(), [&pt](auto it) {return pt == *it; }); 
            });
        point cm2 = *it;
        ++it;
        for (auto ib = it; ib != ust.end(); ++ib)
        {
            if (std::none_of(vit.begin(), vit.end(), [ib](auto it) {return ib == it;}))
            {
                cm2 = cm(cm2, *ib);
            }
        }
        auto dc = std::hypot(cm1.x - cm2.x, cm1.y - cm2.y, cm1.z - cm2.z);
        if (dmin > dc)
        {
            dmin = dc;
            vres = vit;
        }
    }
    else
    {
        for (; ib != ust.end(); )
        {
            vit.push_back(ib);
            ++ib;
            calc(rd - 1, ust, ib);
            vit.pop_back();
        }
    }
}
 
int main() 
{
    system("chcp 1251 > 0");
    std::vector<point> ust{ {0,1,0}, {10,0,0}, {0,0,0}, {10,1,0} }; // множество точек
    for (int i = 0; i < ust.size() / 2; ++i)
    {
        calc(i + 1, ust, ust.begin());
    }
 
    // мин. расстояние между центрами масс
    std::cout << "min distance: " << dmin << "\n";
 
    // одно из двух множеств 
    for (auto it : vres)
    {
        std::cout << *it << " ";
    }
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
22.03.2022, 22:58
Помогаю со студенческими работами здесь

Даны два прямоугольника. Множества А и В - это множества точек, принадлежащих соответствующим прямоугольникам
Даны два прямоугольника. Множества А и В - это множества точек, принадлежащих соответствующим прямоугольникам. Координаты точек - это...

Два множества точек.Треугольник с вершинами в трех из них содержит равное количество точек.
Здравствуйте, помогите пожалуйста решить задачку в mathcad Текст такой- даны два множества точек на плоскости. Из первого множества...

Даны два множества точек на плоскости. Из первого множества выбрать три различные точки, чтобы треугольник с вершинами
Даны два множества точек на плоскости. Из первого множества выбрать три различные точки, чтобы треугольник с вершинами в этих точках...

Найти два разных треугольника с вершинами в точках данного множества точек и расположенных по разные стороны от оси Ох
Дано множество точек на плоскости. Можно ли найти два разных треугольника с вершинами в точках данного множества и расположенных по разные...

Найти булеан множества Z и любое разбиение множества Y
Есть кто знает мат.логику? Задано универсальное множество U = {1, 2, 3, 4, 5, 6, 7, 8} и множества X = {1, 2, 4, 6, 7}, Y = {2, 3, 5,...


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

Или воспользуйтесь поиском по форуму:
3
Ответ Создать тему
Новые блоги и статьи
Система безопасности+живучести для сервера-слоя интернета (сети). Двойная привязка.
Hrethgir 08.04.2026
Далее были размышления о системе безопасности. Сообщения с наклонным текстом - мои. А как нам будет можно проверить, что ссылка наша, а не подделана хулиганами, которая выбросит на другую ветку и. . .
Модель ЗдрввоСохранения 7: больше работников, больше ресурсов.
anaschu 08.04.2026
работников и заданий может быть сколько угодно, но настроено всё так, что используется пока что только 20% kYBz3eJf3jQ
Дальние перспективы сервера - слоя сети с космологическим дизайном интефейса карты и логики.
Hrethgir 07.04.2026
Дальнейшее ближайшее планирование вывело к размышлениям над дальними перспективами. И вот тут может быть даже будут нужны оценки специалистов, так как в дальних перспективах всё может очень сильно. . .
Горе от ума
kumehtar 07.04.2026
Эта мне ментальная установка, что вот прямо сейчас, мол, мне для полного счастья не хватает (нужное вписать), и когда я этого достигну - тогда и полный кайф. Одна из самых сильных ловушек на пути. . . .
Использование значений реквизитов справочника в документе, с определенными условиями и правами
Maks 07.04.2026
1. Контроль срока действия договора Алгоритм из решения ниже реализован на примере нетипового документа "ЗаявкаНаРаботу", разработанного в конфигурации КА2. Задача: уведомлять пользователя, если. . .
Доступность команды формы по условию
Maks 07.04.2026
Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: сделать доступной кнопку (команда формы "ЗавершитьСписание") при. . .
Уведомление о неверно выбранном значении справочника
Maks 06.04.2026
Алгоритм из решения ниже реализован на примере нетипового документа "НарядПутевка", разработанного в конфигурации КА2. Задача: уведомлять пользователя, если в документе выбран неверный склад. . .
Установка Qt Creator для C и C++: ставим среду, CMake и MinGW без фреймворка Qt
8Observer8 05.04.2026
Среду разработки Qt Creator можно установить без фреймворка Qt. Есть отдельный репозиторий для этой среды: https:/ / github. com/ qt-creator/ qt-creator, где можно скачать установщик, на вкладке Releases:. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru