2 / 2 / 0
Регистрация: 16.01.2015
Сообщений: 50
1

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

16.01.2015, 13:00. Показов 2002. Ответов 4
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Помогите пожалуйста....Дана задача: Из заданного множества точек на плоскости выбрать 3 разные точки A,B,C так, чтобы внутри треугольника ABC содержалось максимальное количество точек этого множества. Количество точек вывести тоже....вот никак представить даже не могу как это может выглядеть...буду рад помощи)))
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
16.01.2015, 13:00
Ответы с готовыми решениями:

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

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

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

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

4
34 / 34 / 16
Регистрация: 11.01.2015
Сообщений: 130
16.01.2015, 13:06 2
Гм. Сколько точек?
1. Если несколько десятков - то можно грубо перебрать. Могу позже попытаться написать такую программу.
2. Если "тысячи их" то увы, и надо пытаться придумать человечный алгоритм.
0
Диссидент
Эксперт C
27706 / 17322 / 3812
Регистрация: 24.12.2010
Сообщений: 38,979
16.01.2015, 13:39 3
Ronin94, Для определения того, лежит ли точка М в треугольнике АВС, может пригодиться такое правило. Точка М и вершина С должны лежать по одну сторону от прямой АВ (и так для всех трех вершин). Для определения стороны, по которую точка лежит от прямой надо просто подставить координаты точки в уравнение прямой. Получившийся знак указывает сторону.

Добавлено через 4 минуты
Цитата Сообщение от SuurKissat Посмотреть сообщение
Если "тысячи их" то увы, и надо пытаться придумать человечный алгоритм.
Что-нибудь типа ветвей и границ, да?
Один из подходов (очевидный). Пусть фиксируются 2 точки АВ. И берется 3-я вершина С. Если какие-то точки попадают в треугольник АВС, их вместе с АВ можно уже не рассматривать.
Но наверное, есть подходы и поинтереснее...
0
2 / 2 / 0
Регистрация: 16.01.2015
Сообщений: 50
16.01.2015, 14:31  [ТС] 4
Нет я не знаю как прогу составить вообще....не понимаю толком...с чего начать чем закончить
0
Эксперт по математике/физикеЭксперт С++
2044 / 1363 / 393
Регистрация: 16.05.2013
Сообщений: 3,498
Записей в блоге: 6
16.01.2015, 16:14 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
61
62
63
64
65
66
67
68
#include <iostream>
#include <vector>
struct point {
    double x;
    double y;
};
struct polygon {
    int i1;
    int i2;
    int i3;
    int count;
};
int FindCountVertexIn(const point& a, const point& b, const point& c, const point& pt) {
    if (
        ((b.x - a.x) * (pt.y - a.y) - (b.y - a.y) * (pt.x - a.x) > 0) &&
        ((c.x - b.x) * (pt.y - b.y) - (c.y - b.y) * (pt.x - b.x) > 0) &&
        ((a.x - c.x) * (pt.y - c.y) - (a.y - c.y) * (pt.x - c.x) > 0)
    )
        return 1;
    return 0;
}
int main() {
    const int SIZE = 10;
    point mass[SIZE] = {
                        {0, 0}, {0, 1}, {1, 1}, {1, 0}, {2, 2},
                        {-1, -1}, {-1, 0}, {0, -1}, {-1, 1}, {1, -1}
                        };
    polygon pl_temp;
    std::vector<polygon> coll;
    for(int i = 0; i < SIZE - 2; ++i)
        for(int k = i + 1; k < SIZE - 1; ++k)
            for(int m = k + 1; m < SIZE; ++m) {
                pl_temp.i1 = i;
                pl_temp.i2 = k;
                pl_temp.i3 = m;
                pl_temp.count = 0;
                for(int s = 0; s < SIZE; ++s) {
                    if (
                        (s == i) ||
                        (s == k) ||
                        (s == m)
                        )
                        continue;
                    pl_temp.count += FindCountVertexIn(
                                                        mass[i],
                                                        mass[k],
                                                        mass[m],
                                                        mass[s]
                                                        );
                }
                coll.push_back(pl_temp);
            }
    std::cout << "====================== debug ======================\n";
    for(int n = 0; n < coll.size(); ++n)
        std::cout << coll[n].i1 << ' ' << coll[n].i2 << ' ' << coll[n].i3 << ' ' << coll[n].count << '\n';
    std::cout << "==================== end debug ====================\n";
    int id_max = 0;
    for(int n = 0; n < coll.size(); ++n)
        if (coll[n].count > coll[id_max].count)
            id_max = n;
    std::cout << "polygon(x, y, z, count) : ";
    std::cout << coll[id_max].i1 << ' '
              << coll[id_max].i2 << ' '
              << coll[id_max].i3 << ' '
              << coll[id_max].count << '\n';
 
    return 0;
}
0
16.01.2015, 16:14
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
16.01.2015, 16:14
Помогаю со студенческими работами здесь

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

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

Выбрать из множества три разные точки так, чтобы внутри треугольника содержалось максимальное количество точек
Задача такова : Из заданного множества точек на плоскости выбрать три разные точки А В С так,...

Из заданного множества точек на плоскости выбрать три разные точки A, B и C так, чтобы внутри треугольника ABC содержалось максимальное количество точ
Из заданного множества точек на плоскости выбрать три разные точки A, B и C так, чтобы внутри...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru