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

@Lokid · Регистрация: 24.11.2014

Студворк — интернет-сервис помощи студентам

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

Нашёл подобную задачу с решением,но там дан треугольник. Переделал под квадрат, но теперь программа не выдаёт площадь и пишет только:
"Не найдено точек, чтобы покрыть квадратом всё второе множество!"
Помогите, пожалуйста. Уже голова кругом.

Вот исходник:

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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
#include <iostream>
#include <ctime>
#include <cmath>
#include <conio.h>
 
using namespace std;
 
int **first_arr, **second_arr; //множества точек
 
bool unique(int x, int y, int **arr, int n)//проверяем,является ли точка единственной в множестве
{
    for (int i = 0; i < n; i++)
    {
 
        if (arr[0][i] == x && arr[1][i] == y)
            return false;
    }
    return true;
}
void generate_arr(int n, int m)
{
    srand(time(0));
 
    first_arr = new int*[2];
    second_arr = new int*[2];
    
        first_arr[0] = new int [n];
        second_arr[0] = new int[m];
        first_arr[1] = new int[n];
        second_arr[1] = new int[m];
 
        int x, y;
        for (int j = 0; j < n; j++)
        {
            do
            {
                x = rand() % 100;
                y = rand() % 100;
            } while (!unique(x, y, first_arr, n));
 
            first_arr[0][j] = x;
            first_arr[1][j] = y;
        }
 
        for (int j = 0; j < m; j++)
        {
            do
            {
                x = rand() % 100;
                y = rand() % 100;
            } while (!unique(x, y, second_arr, m));
 
            second_arr[0][j] = x;
            second_arr[1][j] = y;
        }
}
void show_arr(int n, int m)
{
    cout << "Первое множество :\n";
    for (int i = 0; i < n; i++)
        cout << (i + 1) << ") x = " << first_arr[0][i] << ", y = " << first_arr[1][i] << endl;
 
    cout << "\nВторое множество :\n";
    for (int i = 0; i < m; i++)
        cout << (i + 1) << ") x = " << second_arr[0][i] << ", y = " << second_arr[1][i] << endl;
}
bool isTriangle(double a, double b, double c)//проверяем, являются ли отрезки треугольником 
{
    if ((a + b - c < 0) || (a + c - b < 0) || (b + c - a < 0))
        return false;
    return true;
}
 
double square(double a, double b, double c)
{
    return sqrt((a + b + c) * (b + c - a) * (a + c - b) * (a + b - c)) / 4.0;
}
double distanceBetweenPoints(int x1, int y1, int x2, int y2)
{
    double d = 0;
    d = (x1 - x2)*(x1 - x2) + (y1 - y2)*(y1 - y2);
 
    return sqrt(d);
}
 
int area(int x1, int y1, int x2, int y2, int x3, int y3)
{
    return abs((x1 - x3)*(y2 - y3) + (x2 - x3)*(y3 - y1));
}
bool checkFirstCoversSecond(int x1, int y1, int x2, int y2, int x3, int y3, int **arr, int m)
{
    for (int i = 0; i < m; i++)
    {
        if (!(area(x1, y1, x2, y2, x3, y3) == area(x1, y1, x2, y2, arr[0][i], arr[1][i]) + area(x1, y1, arr[0][i], arr[1][i], x3, y3) + area(x2, y2, arr[0][i], arr[1][i], x3, y3)))
            return false;
    }
    return true;
}
double min_square(int **arr, int n, int m)
{
    double a, b, c; //стороны нашего треугольника
 
    double minS = DBL_MAX;
    double S;
 
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
        for (int z = j + 1; z < n; z++)
        {
            if (checkFirstCoversSecond(arr[0][i], arr[1][i], arr[0][j], arr[1][j], arr[0][z], arr[1][z], second_arr, m))
            {
                a = distanceBetweenPoints(arr[0][i], arr[1][i], arr[0][j], arr[1][j]);
                b = distanceBetweenPoints(arr[0][i], arr[1][i], arr[0][z], arr[1][z]);
                c = distanceBetweenPoints(arr[0][z], arr[1][z], arr[0][j], arr[1][j]);
                if (isTriangle(a, b, c))
                {
                    S = square(a, b, c);
                    cout << "\nТочки - (" << arr[0][i] << ", " << arr[1][i] << ")-(" << arr[0][j] << ", " << arr[1][j] << ")-(" << arr[0][z] << ", " << arr[1][z] << ") --- накрывают все точки второго множества!\n";
                    cout << "Площадь треугольника с вершинами в этих точках = " << S << endl;
                    if (S < minS) { minS = S; }
                }
                else
                {
                    cout << "Не являются треугольником!!!\n";
                }
            }
            
 
        }
        if (minS != DBL_MAX)
            cout << "\n\nМинимальную площадь = " << minS << endl;
        else
            cout << "\n\nНе найдено точек, чтобы покрыть треугольником всё второе множество!" << endl;
    return 0;
}
 
void main()
{
    setlocale(LC_ALL, "Russian");
 
    int n, m; //количество точек в множествах
 
    cout << "Введите количество точек первого множества - ";
    cin >> n;
 
    cout << "Введите количество точек второго множества - ";
    cin >> m;
 
    generate_arr(n, m);
    show_arr(n, m);
 
    min_square(first_arr, n, m);
    getch();
}

Вот исправленная:

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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
#include <iostream>
#include <ctime>
#include <cmath>
#include <conio.h>
 
using namespace std;
 
int **first_arr, **second_arr; //множества точек
 
bool unique(int x, int y, int **arr, int n)//проверяем, является ли точка единственной в множестве
{
    for (int i = 0; i < n; i++)
    {
 
        if (arr[0][i] == x && arr[1][i] == y)
            return false;
    }
    return true;
}
 
void generate_arr(int n, int m)
{
    first_arr = new int*[2];
    second_arr = new int*[2];
    
        first_arr[0] = new int [n];
        second_arr[0] = new int[m];
        first_arr[1] = new int[n];
        second_arr[1] = new int[m];
 
        int x, y;
        for (int i = 0; i < n; i++)
        {
          cout << "x[" << i+1 << "]=";
          cin >> first_arr[0][i];
          cout << "y[" << i+1 << "]=";
          cin >> first_arr[1][i];
        }
        cout<<endl<<endl;       
    
        for (int i = 0; i < m; i++)
        {
          cout << "x[" << i+1  << "]=";
          cin >> second_arr[0][i];
          cout << "y[" << i+1 << "]=";
          cin >> second_arr[1][i];
        }
        cout<<endl<<endl;
}
 
void show_arr(int n, int m)
{
    cout << "Первое множество:\n";
    for (int i = 0; i < n; i++)
        cout << (i + 1) << ") x = " << first_arr[0][i] << ", y = " << first_arr[1][i] << endl;
 
    cout << "\nВторое множество:\n";
    for (int i = 0; i < m; i++)
        cout << (i + 1) << ") x = " << second_arr[0][i] << ", y = " << second_arr[1][i] << endl;
}
 
bool isTriangle(double a, double b, double c, double d)//являются ли отрезки квадратом 
{
    if (!((a == b) || (b == c) || (c == d) || (d == a)))
        return false;
    return true;
}
 
double square(double a, double b, double c, double d)//площадь квадрата через стороны
{
    return sqrt((a+b+c-d)*(a+b+d-c)*(a+c+d-b)*(b+c+d-a))/4;
}
 
double distanceBetweenPoints(int x1, int y1, int x2, int y2)//расстояние между точками
{
    double D = 0;
    D = (x1 - x2)*(x1 - x2) + (y1 - y2)*(y1 - y2);
    return sqrt(D);
}
 
int area(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4)//площадь через координаты вершин
{
    return ((x1 - x2)*(x3 - x4) + (y1 - y2)*(y3 - y4)); //??????? 
}
 
bool checkFirstCoversSecond(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4, int **arr, int m)
{
    for (int i = 0; i < m; i++)
    {
        if (!(area(x1, y1, x2, y2, x3, y3, x4, y4) == area(x1, y1, x2, y2, arr[0][i], arr[1][i], x4, y4) + area(x1, y1, arr[0][i], arr[1][i], x3, y3, x4, y4) + area(x2, y2, arr[0][i], arr[1][i], x3, y3, x4, y4)+area(x1, y1, x2, y2, x3, y3, arr[0][i], arr[1][i])))
            return false;
    }
    return true;
}
 
double min_square(int **arr, int n, int m)
{
    double a, b, c, d; 
 
    double minS = DBL_MAX;
    double S;
 
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
        for (int z = j + 1; z < n; z++)
        for (int k = z + 1; k < n; k++)
        {
            if (checkFirstCoversSecond(arr[0][i], arr[1][i], arr[0][j], arr[1][j], arr[0][z], arr[1][z], arr[0][k], arr[1][k], second_arr, m))
            {
                a = distanceBetweenPoints(arr[0][i], arr[1][i], arr[0][j], arr[1][j]);
                b = distanceBetweenPoints(arr[0][j], arr[1][j], arr[0][k], arr[1][k]);
                c = distanceBetweenPoints(arr[0][k], arr[1][k], arr[0][z], arr[1][z]);
                d = distanceBetweenPoints(arr[0][z], arr[1][z], arr[0][i], arr[1][i]);
                if (isTriangle(a, b, c, d))
                {
                    S = square(a,b,c,d);
                    cout << "\nТочки - (" << arr[0][i] << ", " << arr[1][i] << ")-(" << arr[0][j] << ", " << arr[1][j] << ")-(" << arr[0][z] << ", " << arr[1][z] << ")-(" << arr[0][k] << ", " << arr[1][k] << ") --- накрывают все точки второго множества!\n";
                    cout << "Площадь квадрата с вершинами в этих точках = " << S << endl;
                    if (S < minS) { minS = S; }
                }
                else
                {
                    cout << "Не являются Квадратом!!!\n";
                }
            }
        
        }
        if (minS != DBL_MAX)
            cout << "\n\nМинимальную площадь = " << minS << endl;
        else
            cout << "\n\nНе найдено точек, чтобы покрыть квадратом всё второе множество!" <<endl;
    return 0;
}
 
void main()
{
    setlocale(LC_ALL, "Russian");
    int n, m; 
    cout << "Введите количество точек первого множества - ";
    cin >> n;
    cout << "Введите количество точек второго множества - ";
    cin >> m;
    generate_arr(n, m);
    show_arr(n, m);
    min_square(first_arr, n, m);
    getch();
}

Новые блоги и статьи Все статьи Все блоги /
Переходник USB-CAN-GPIO Eddy_Em 20.03.2026 Достаточно давно на работе возникла необходимость в переходнике CAN-USB с гальваноразвязкой, оный и был разработан. Однако, все меня терзала совесть, что аж 48-ногий МК используется так тупо: просто. . .	Оттенки серого Argus19 18.03.2026 Оттенки серого Нашёл в интернете 3 прекрасных модуля: Модуль класса открытия диалога открытия/ сохранения файла на Win32 API; Модуль класса быстрого перекодирования цветного изображения в оттенки. . .	SDL3 для Desktop (MinGW): Рисуем цветные прямоугольники с помощью рисовальщика SDL3 на Си и C++ 8Observer8 17.03.2026 Содержание блога Финальные проекты на Си и на C++: finish-rectangles-sdl3-c. zip finish-rectangles-sdl3-cpp. zip	Символические и жёсткие ссылки в Linux. algri14 15.03.2026 Существует два типа ссылок — символические и жёсткие. Ссылка в Linux — это запись в каталоге, которая может указывать либо на inode «файла-ИСТОЧНИКА», тогда это будет «жёсткая ссылка» (hard link),. . .
[Owen Logic] Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ФедосеевПавел 14.03.2026 Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ВВЕДЕНИЕ Выполняя задание на управление насосной группой заполнения резервуара,. . .	делаю науч статью по влиянию грибов на сукцессию anaschu 13.03.2026 прикрепляю статью	SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:	Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .