ВНИМАНИЕДля получения программы своего варианта пишите на наш электронный адрес 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)

Условие задачи

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

Реализация задачи на языке С++

Результаты работы программы

Детально рассмотрим результаты работы программы, когда на вход подаются $14$ точек:

Заданное множество точек

Программа должна обнаружить следующие квадраты:

Обнаружен квадрат №1

Найденный квадрат №2

Найденный квадрат №3

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

➡ Обращаем ваше внимание, что точки, являющиеся вершинами самого квадрата, не учитываются.

Квадрат, в котором больше всего точек

Официальные результаты программы

💡 Программа достаточно сложная и объемная. При большом количестве входных точек резко снижается ее производительность. Поэтому рекомендуем тестировать программу, подавая на вход не более $50\ -\ 100$ точек.

ВНИМАНИЕДля получения программы своего варианта пишите на наш электронный адрес proglabs@mail.ru