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

Из множества выбрать три различные точки по условию

29.06.2015, 14:43. Показов 1319. Ответов 4
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Даны два множества точек на плоскости. Из первого множества выбрать три различные точки так, чтобы треугольник с вершинами в этих точках содержал внутри себя максимальное количество точек второго множество
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
29.06.2015, 14:43
Ответы с готовыми решениями:

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

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

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

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

4
Диссидент
Эксперт C
27706 / 17322 / 3812
Регистрация: 24.12.2010
Сообщений: 38,979
29.06.2015, 19:31 2
penek81, Что ж. С точки зрения программирования - обычная переборная задача. Какие именно моменты представляют затруднения?
0
0 / 0 / 0
Регистрация: 11.01.2015
Сообщений: 19
29.06.2015, 19:53  [ТС] 3
треугольник с вершинами в этих точках содержал внутри себя максимальное количество точек второго множество
0
Диссидент
Эксперт C
27706 / 17322 / 3812
Регистрация: 24.12.2010
Сообщений: 38,979
29.06.2015, 21:23 4
Цитата Сообщение от penek81 Посмотреть сообщение
Из первого множества выбрать три различные точки так, чтобы треугольник с вершинами в этих точках содержал внутри себя максимальное количество точек второго множество
Цитата Сообщение от Байт Посмотреть сообщение
Какие именно моменты представляют затруднения?
Цитата Сообщение от penek81 Посмотреть сообщение
треугольник с вершинами в этих точках содержал внутри себя максимальное количество точек второго множество
Классный ответ!
Дальнейшая дискуссия на эту тему мне как-то представляется лишенной какого-либо смысла...
0
193 / 100 / 131
Регистрация: 23.06.2015
Сообщений: 249
30.06.2015, 12:58 5
Лучший ответ Сообщение было отмечено penek81 как решение

Решение

Перебор за https://www.cyberforum.ru/cgi-bin/latex.cgi?O(\frac{{n}^{3}m}{6}), где n - число точек в первом множестве, m - число точек во втором множестве

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
#include <stdio.h>
#include <stdlib.h>
 
typedef struct tag_point
{
    int x;
    int y; 
} Point;
 
Point *fiSet;
Point *seSet;
 
int Q(int ax, int ay, int bx, int by, int atx, int aty)
{
    return atx * (by - ay) + aty * (ax - bx) + ay * bx - ax * by;
}
 
int Check(int aAx, int aAy, int aBx, int aBy, int aCx, int aCy, int aPx, int aPy)
{
    int q1 = Q(aAx, aAy, aBx, aBy, aPx, aPy);
    int q2 = Q(aBx, aBy, aCx, aCy, aPx, aPy);
    int q3 = Q(aCx, aCy, aAx, aAy, aPx, aPy);
    if ( ((q1 >= 0) && (q2 >= 0) && (q3 >= 0)) || ((q1 < 0) && (q2 < 0) && (q3 < 0)) ) return 1; else return 0;
}
 
int main()
{
    int n, m, i, j, k, x, y, g, l;
    scanf("%d", &n); //n - число точек в первом множестве
    scanf("%d", &m); //m - число точек во втором множестве
    
    fiSet = (Point*)malloc(sizeof(Point) * n);
    seSet = (Point*)malloc(sizeof(Point) * m);
    
    for(i = 0; i < n; i++)
    {
        scanf("%d", &x);
        scanf("%d", &y);
        fiSet[i].x = x;
        fiSet[i].y = y;
    }
    
    for(i = 0; i < m; i++)
    {
        scanf("%d", &x);
        scanf("%d", &y);
        seSet[i].x = x;
        seSet[i].y = y;
    }
    
    Point p[3];
    int iHavePoints = -1;
    
    for(i = 0; i < n; ++i)
        for(j = i + 1; j < n; ++j)
            for(k = j + 1; k < n; ++k)
            {
                g = 0;
                
                for(l = 0; l < m; l++) 
                    g += Check(fiSet[i].x, fiSet[i].y, 
                               fiSet[j].x, fiSet[j].y, 
                               fiSet[k].x, fiSet[k].y, 
                               seSet[l].x, seSet[l].y);
                
                if(g > iHavePoints) 
                { 
                    iHavePoints = g; 
                    p[0].x = fiSet[i].x; p[0].y = fiSet[i].y;
                    p[1].x = fiSet[j].x; p[1].y = fiSet[j].y;
                    p[2].x = fiSet[k].x; p[2].y = fiSet[k].y;
                }
            }
    
        //Выводим три искомые точки
    printf("%d %d\n", p[0].x, p[0].y);
    printf("%d %d\n", p[1].x, p[1].y);
    printf("%d %d\n", p[2].x, p[2].y);
    
    free(fiSet);
    free(seSet);
    
    return 0;
}
1
30.06.2015, 12:58
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
30.06.2015, 12:58
Помогаю со студенческими работами здесь

Из множества выбрать три различные точки по условию -из Turbo Pascal во Free Pascal
Даны 2 множества точек на плоскости. Выбрать три различные точки первого множества так, чтобы круг...

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

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

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


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

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

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