Содержание
ВНИМАНИЕ | Для получения программы своего варианта пишите на наш электронный адрес proglabs@mail.ru |
Варианты заданий
№ | Условие |
1 | Два выпуклых многоугольника заданы на плоскости перечислением координат вершин в порядке обхода границы. Определить площади многоугольников и проверить, лежит ли один из них строго внутри другого. |
2 | Из заданного на плоскости множества точек выбрать три различные точки так, чтобы разность между площадью круга, ограниченного окружностью, проходящей через эти три точки, и площадью треугольника с вершинами в этих точках была минимальной. |
3 | Даны два множества точек на плоскости. Выбрать три различные точки первого множества так, чтобы круг, ограниченный окружностью, проходящей через эти три точки, содержал все точки второго множества и имел минимальную площадь. |
4 | Даны два множества точек на плоскости. Выбрать четыре различные точки первого множества так, чтобы квадрат с вершинами в этих точках накрывал все точки второго множества и имел минимальную площадь. |
5 | Даны два множества точек на плоскости. Выбрать три различные точки первого множества так, чтобы треугольник с вершинами в этих точках накрывал все точки второго множества и имел минимальную площадь. |
6 | Даны два множества точек на плоскости. Найти радиус и центр окружности, проходящей через $n$ ($n \geq 3$) точек первого множества и содержащей строго внутри себя равное число точек первого и второго множеств. |
7 | Даны два множества точек на плоскости. Из первого множества выбрать три различные точки так, чтобы треугольник с вершинами в этих точках содержал (строго внутри себя) равное количество точек первого и второго множеств. |
8 | На плоскости заданы множество точек $M$ и круг. Выбрать из $M$ две различные точки так, чтобы наименьшим образом различались количества точек в круге, лежащей по разные стороны от прямой, проходящей через эти точки. |
9 | Дано $3n$ точек на плоскости, причем никакие три из них не лежат на одной прямой. Построить множество $n$ треугольников с вершинами в этих точках так, чтобы никакие два треугольника не пересекались и не содержали друг друга. |
10 | Выбрать три различные точки из заданного множества точек на плоскости так, чтобы была минимальной разность между количеством точек, лежащих внутри и вне треугольника с вершинами в выбранных точках. |
11 | Определить радиус и центр окружности, проходящей по крайней мере через три различные точки заданного множества точек на плоскости и содержащей внутри наибольшее количество точек этого множества. |
12 | На плоскости заданы множество точек $A$ и точка $d$ вне его. Подсчитать количество различных неупорядоченных троек точек $a,\ b,\ c$ из $A$ таких, что четырехугольник $abcd$ является параллелограммом. |
13 | На плоскости заданы множества точек $A$ и множество окружностей $B$. Найти две такие различные точки из $A$, что проходящая через них прямая пересекается с максимальным количеством окружностей из $B$. |
14 | Задано множество точек на плоскости. Найти все четверки точек, являющихся вершинами квадратов. Найти квадрат, внутри которого лежит наибольшее количество точек множества. |
15 | Определить радиус и центр окружности минимального радиуса, проходящей хотя бы через три различные точки заданного множества точек на плоскости. |
16 | Найти три треугольника с вершинами множестве точек на плоскости так, чтобы второй треугольник лежал строго внутри первого, а третий внутри второго. |
17 | Дано множество точек на плоскости. Построить все возможные треугольники с вершинами в этом множестве точек и найти среди них такой, стороны которого пересекаются с максимальным количеством треугольников. |
18 | На плоскости заданы множество точек и окружность радиусом $R$ с центром в начале координат. Построить множество всех треугольников с вершинами в заданных точках, все три стороны которых пересекаются с окружностью, и найти среди них треугольник с минимальной площадью. |
19 | Подсчитать количество равносторонних треугольников с различными длинами оснований и вершинами в заданном множестве точек на плоскости и определить, пересекаются ли они. |
20 | Множество попарно различных плоскостей в трехмерном пространстве задано перечислением троек точек, через которые проходит каждая из плоскостей. Выбрать максимальное подмножество попарно непараллельных плоскостей. |
Образец выполнения (вариант №14)
Условие задачи
Задано множество точек на плоскости. Найти все четверки точек, являющихся вершинами квадратов. Найти квадрат, внутри которого лежит наибольшее количество точек множества.
Реализация задачи на языке С++
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 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 | #include <iostream> // для консольного ввода-вывода #include <random> #include <time.h> #include <iomanip> // для форматированного вывода #include <string> // для работы со строками using namespace std; // описание сущности "Точка" typedef struct TPoint { double x; // значение координаты по оси абсцисс double y; // значение координаты по оси ординат } Point; double Get_square_distance_between_points( const Point p1, const Point p2 ); // ввод количества точек для обработки size_t Get_points_count( void ) { // максимальное количество точек для обработки const int MAX = 100; int count; do { cout << "Введите количество точек для обработки из отрезка [4 ... " << MAX << "]: "; cin >> count; } while ( ( count < 4 ) || ( count > MAX ) ); return ( size_t )count; } // заполнение массива точек из points_count штук вводом с клавиатуры Point* Input_points_from_keyboard( const size_t points_count ) { Point* points = new Point[ points_count ]; for ( size_t i = 0; i < points_count; i++ ) { cout << "\t - ведите координаты точки №" << ( i + 1 ) << ": "; cin >> points[ i ].x >> points[ i ].y; } return points; } // заполнение массива точек из points_count штук случайными дробными числами из отрезка [left_border; right_border] Point* Input_points_random_value( const size_t points_count, const double left_border, const double right_border ) { Point* points = new Point[ points_count ]; //// настраиваем профессиональный генератор случайных ДРОБНЫХ чисел //default_random_engine engine( time( 0 ) ); //uniform_real_distribution<> my_random( left_border, right_border ); //for ( size_t i = 0; i < points_count; i++ ) //{ // points[ i ].x = my_random( engine ); // points[ i ].y = my_random( engine ); //} // для получения квадратов для проверки результата будем генерировать целые числа srand( time( 0 ) ); for ( size_t i = 0; i < points_count; i++ ) { points[ i ].x = rand() % 21 - 10; points[ i ].y = rand() % 21 - 10; } return points; } // вывод координат вершин квадрата на экран void Print_square( const Point a, const Point b, const Point c, const Point d, const string message ) { cout << message << endl; cout << "\tA(" << a.x << "; " << a.y << "), "; cout << "B(" << b.x << "; " << b.y << "), "; cout << "C(" << c.x << "; " << c.y << "), "; cout << "D(" << d.x << "; " << d.y << ")" << endl; } // формула Герона для нахождения площади треугольника через его длины сторон // на вход функция принимает координаты вершин треугольника double Geron( const Point A, const Point B, const Point C ) { double AB = sqrt( Get_square_distance_between_points( A, B ) ); double BC = sqrt( Get_square_distance_between_points( B, C ) ); double AC = sqrt( Get_square_distance_between_points( A, C ) ); // находим полупериметр треугольника double p = 0.5 * ( AB + BC + AC ); // вычисляем площадь по формуле s = sqrt(p(p - a)(p - b)(p - c )) return ( sqrt( p * ( p - AB ) * ( p - BC ) * ( p - AC ) ) ); } // проверка точки на попадание в квадрат bool Is_point_in_square( const Point A, const Point B, const Point C, const Point D, const Point O, const double square_side ) { // заданную точку соединяем со всеми вершинами квадрата ABCD // при этом образуется 4ре треугольника: OAB, OBC, OCD, OAD // если сумма площадей этих 4рех треугольников равна площади квадрата ABCD, то точка попадает внутрь квадрата double Soab = Geron( O, A, B ); double Sobc = Geron( O, B, C ); double Socd = Geron( O, C, D ); double Soad = Geron( O, A, D ); // площадь квадрата double Sabcd = square_side; // точность сравнения вещественных чисел const double EPS = 0.0001; bool result = false; if ( Soab + Sobc + Socd + Soad - Sabcd <= EPS ) result = true; return result; } // получение квадрата расстояния между 2мя точками на плоскости double Get_square_distance_between_points( const Point p1, const Point p2 ) { double distance = pow( p2.x - p1.x, 2.0 ) + pow( p2.y - p1.y, 2.0 ); return distance; } // проверка на "почти" квадрат // side1 в 2 раза больше side2/side3, а side2 = side3 bool Is_almost_square( const double side1, const double side2, const double side3 ) { const double EPS = 0.001; // точность сравнения double-ов bool result = false; if ( ( fabs( side2 - side3 ) <= EPS ) && ( fabs( side1 - 2*side2 ) <= EPS ) ) result = true; return result; } // определение номера диагональной вершины с проверкой четырехугольника на квадрат (b - 2, c - 3, d - 4) // вернется 0, если данный четырехугольник НЕ является даже претендентом на квадратом! size_t Get_number_diagonal_vertex( const Point a, const Point b, const Point c, const Point d ) { // получаем квадраты расстояний от точки А до каждой из точек B, C, D (AB, AC, AD) double AB = Get_square_distance_between_points( a, b ); double AC = Get_square_distance_between_points( a, c ); double AD = Get_square_distance_between_points( a, d ); // если любой из отрезков (например, АВ) равен 0, то это уже 100% не квадрат if ( AB > 0 ) { // проверка вершины В на диагональность (диагональ АВ) if ( Is_almost_square( AB, AC, AD ) == true ) return 2; // проверка вершины С на диагональность (диагональ АС) if ( Is_almost_square( AC, AB, AD ) == true ) return 3; // проверка вершины D на диагональность (диагональ AD) if ( Is_almost_square( AD, AB, AC ) == true ) return 4; } return 0; } // проверка на квадрат по 4рем точкам // должны быть равны длины всех сторон (или их квадраты), а также длины диагоналей (или их квадраты) bool Is_square( const Point a, const Point b, const Point c, const Point d ) { // квадраты длин сторон потенциального квадрата double AB = Get_square_distance_between_points( a, b ); double BC = Get_square_distance_between_points( b, c ); double CD = Get_square_distance_between_points( c, d ); double AD = Get_square_distance_between_points( a, d ); // квадраты длин диагоналей потенциального квадрата double AC = Get_square_distance_between_points( a, c ); double BD = Get_square_distance_between_points( b, d ); bool result = false; const double EPS = 0.001; // точность сравнения double-ов // проверка равенства квадратов длин сторон if ( ( fabs( AB - BC ) <= EPS ) && ( fabs ( BC - CD ) <= EPS ) && ( fabs( CD - AD ) <= EPS ) ) // добавляем проверку диагоналей (или их квадратов) if ( fabs( AC - BD ) <= EPS ) result = true; // вот теперь доказано, что данный четырехугольник квадрат return result; } // сравнение двух точек на полное глубокое равенство между собой bool Is_equal_2_points( const Point &p1, const Point &p2 ) { const double EPS = 0.001; // точность сравнения double-ов if ( ( fabs( p1.x - p2.x ) <= EPS ) && ( fabs( p1.y - p2.y ) <= EPS ) ) return true; return false; } // перебор всех точек в поиске квадратов size_t Get_all_squares( const Point* points, const size_t points_count ) { // количество найденных квадратов size_t squares_count = 0; // количество точек, входящих в текущий (только что найденный) квадрат size_t current_points_count = 0; // максимальное количество точек, входящих в квадрат size_t max_points_count = 0; // вершины квадрата, внутрь которого попадает максимальное количество точек Point maxA, maxB, maxC, maxD; // перебираем все возможные четверки точек (т к квадрат имеет четыре вершины) // сложность перебора O(N^4) cout << endl; for ( register size_t i = 0; i < ( points_count - 3 ); i++ ) for ( register size_t j = ( i + 1 ); j < ( points_count - 2 ); j++ ) for ( register size_t k = ( j + 1 ); k < ( points_count - 1 ); k++ ) for ( register size_t l = ( k + 1 ); l < points_count; l++ ) { Point A = points[ i ]; // точка points[ i ] принимается за вершину А Point B = points[ j ]; // точка points[ j ] принимается за вершину В Point C = points[ k ]; // точка points[ k ] принимается за вершину C Point D = points[ l ]; // точка points[ l ] принимается за вершину D // квадрат стороны квадрата (по сути - его площадь) double square_side; bool is_square; // пробуем найти диагональную вершину по отношению к точке А (это будет кандидат на квадрат!) // number = -1, если четырехугольник 100% не квадрат size_t number = Get_number_diagonal_vertex( A, B, C, D ); switch ( number ) { case 2: // кандидат в квадраты ACBD { if ( is_square = ( Is_square( A, C, B, D ) == true ) ) { squares_count++; Print_square( A, C, B, D, "Найден новый квадрат со следующими координатами: " ); square_side = Get_square_distance_between_points( A, C ); } break; } case 3: // кандидат в квадраты ABCD { if ( is_square = ( Is_square( A, B, C, D ) == true ) ) { squares_count++; Print_square( A, B, C, D, "Найден новый квадрат со следующими координатами: " ); square_side = Get_square_distance_between_points( A, B ); } break; } case 4: // кандидат в квадраты ABDC { if ( is_square = ( Is_square( A, B, D, C ) == true ) ) { squares_count++; Print_square( A, B, D, C, "Найден новый квадрат со следующими координатами: " ); square_side = Get_square_distance_between_points( A, B ); } break; } } // проверяем каждую точку на попадание внутрь найденного квадрата if ( ( number != 0 ) && ( is_square == true ) ) { current_points_count = 0; for ( size_t ipoint = 0; ipoint < points_count; ipoint++ ) { Point P = points[ ipoint ]; if ( ( Is_equal_2_points( A, P ) == false ) && ( Is_equal_2_points( B, P ) == false ) && ( Is_equal_2_points( C, P ) == false ) && ( Is_equal_2_points( D, P ) == false ) ) if ( Is_point_in_square( A, B, C, D, P, square_side ) ) current_points_count++; } if ( current_points_count > max_points_count ) { max_points_count = current_points_count; maxA = A; maxB = B; maxC = C; maxD = D; } } } // выпечатываем квадрат, в который попало больше всего заданных точек (если он был найден) if ( max_points_count > 0 ) { Print_square( maxA, maxB, maxC, maxD, "\nКоординаты вершин квадрата, внутри которого лежит максимальное количество точек:" ); cout << "В данный квадрат попало " << max_points_count << " шт. точек" << endl; } // в качестве ответа возвращаем кол-во найденных квадратов return squares_count; } // главная функция программы (точка входа) int main( void ) { // русификация диалогов setlocale( LC_ALL, "Russian" ); // количество точек для обработки size_t points_count = Get_points_count(); // оставлено для тестирования на большом количестве точек //Point* points = Input_points_random_value( points_count, -1.0, +1.0 ); // ввод координат точек с клавиатуры Point* points = Input_points_from_keyboard( points_count ); // общее количество квадратов size_t squares_count = Get_all_squares( points, points_count ); cout << "\nВсего было найдено " << squares_count << " шт. квадратов" << endl; // удаляем память из-под множества точек delete[] points; // задержка программы, чтобы у пользователя была возможность просмотреть результат cout << endl << endl; system( "pause" ); return EXIT_SUCCESS; } |
Результаты работы программы
Детально рассмотрим результаты работы программы, когда на вход подаются $14$ точек:
Программа должна обнаружить следующие квадраты:
Последний штрих программы — нахождение квадрата, внутри которого лежит наибольшее количество точек заданного множества.
➡ Обращаем ваше внимание, что точки, являющиеся вершинами самого квадрата, не учитываются.
💡 Программа достаточно сложная и объемная. При большом количестве входных точек резко снижается ее производительность. Поэтому рекомендуем тестировать программу, подавая на вход не более $50\ -\ 100$ точек.
ВНИМАНИЕ | Для получения программы своего варианта пишите на наш электронный адрес proglabs@mail.ru |
Добавить комментарий