Общая информация
В этом разделе даны задания для самостоятельного выполнения. Сначала будут разобраны необходимые для решения этих задач примитивы, после чего будет дан общий алгоритм решения.
Таблица уроков:
| Этап | Коммит | Кол-во уроков |
|---|---|---|
| ReadMe | ReadMe | 1 |
| Элементы управления | Control | 1 |
| Структуры данных | Data Structures | 1 |
| Рисование | Render | 1 |
| Добавление кнопками | Buttons | 1 |
| Добавление мышью | Mouse | 1 |
| Решение задачи | Solve | 1 |
| Работа с файлами | Files | 1 |
| Отчёт | Report | 1 |
| Презентация | Presentation | 1 |
| Защита | - | 2 |
Как получить тройку
В прошлом полугодии у вас должна быть оценка не ниже .
Чтобы получить тройку за проект, вам нужно сделать задания от 08. Разметка до 10. Управление
включительно, плюс добавление мышью из 11. Управление 2
Самостоятельно написанная программа должна обеспечивать следующие пункты:
ReadMe, Элементы управления (только заголовок с текстом задания), Структуры данных,
Рисование, Добавление мышью, Отчёт, Презентация, Защита.
Как получить четвёрку
В прошлом полугодии у вас должна быть оценка не ниже
Чтобы получить четвёрку за проект, вам нужно сделать задания от 08. Разметка до 12. Решение задачи
включительно.
Самостоятельно написанная программа должна обеспечивать следующие пункты:
ReadMe, Элементы управления (кроме кнопок загрузки и сохранения), Структуры данных,
Рисование, Добавление кнопками, Добавление мышью, Решение задачи,
Отчёт, Презентация, Защита.
Решаться задача должна по нажатию кнопки S на клавиатуре, также по кнопке R
решение должно сбрасываться.
Задачи
В этом разделе предложены задачи для самостоятельного решения.
Ссылку на репозиторий нужно прислать здесь.
Чтобы определиться, какую задачу нужно решать, найдите в таблице ваш номер в группе. Таблицы находятся в этом файле.
Задачи составлены Ушаковым Денисом Михайловичем.
На плоскости задано множество точек. Найти среди них такие две пары, что точка пересечения прямых, проведенных через эти пары точек, находится ближе всего к началу координат. То есть, если рассмотреть все возможные прямые, которые могут быть построены по парам указанных точек, и все возможные точки пересечения этих прямых между собой, то нужно найти такую точку пересечения этих прямых, которая находится ближе всего к началу координат. Ответом должна быть: эта точка пересечения, те две прямые, которые в этой точке пересекаются, а также отрезок, проведенный из начала координат до точки пересечения.
На плоскости задано множество точек, и "параллельный" прямоугольник. Множество точек образует все возможные прямые, которые могут быть построены парами точек множества. Найти такую прямую (и такие две точки, через которые она проходит), что эта прямая пересекает указанный прямоугольник, и при этом длина отрезка прямой, находящейся внутри прямоугольника, максимальна. В качестве ответа: выделить найденные две точки, нарисовать прямую, которая через них проходит, а также выделить на этой прямой отрезок между двумя найденными точками пересечения.
На плоскости задано множество точек, и прямоугольник. Множество точек образует все возможные прямые, которые могут быть построены парами точек множества. Найти такую прямую (и такие две точки, через которые она проходит), что эта прямая пересекает указанный прямоугольник, и при этом длина отрезка прямой, находящейся внутри прямоугольника, максимальна. В качестве ответа: выделить найденные две точки, нарисовать прямую, которая через них проходит, а также выделить на этой прямой отрезок между двумя найденными точками пересечения.
На плоскости задано множество точек, и множество окружностей. Множество точек образует все возможные прямые, которые могут быть построены парами точек множества. Найти такую прямую (и такие две точки, через которые она проходит) и такую окружность, что эта прямая пересекает указанную окружность, и при этом длина отрезка прямой, находящейся внутри окружности, максимальна. В качестве ответа: выделить найденные две точки, выделить найденную окружность, нарисовать прямую, которая через них проходит, а также выделить на этой прямой отрезок между двумя найденными точками пересечения.
На плоскости задано множество окружностей. Найти такую пару пересекающихся окружностей, что длина отрезка, проведенного от одной точки пересечения этих двух окружностей до другой, максимальна. В качестве ответа: выделить эту пару окружностей, нарисовать отрезок между найденными точками пересечения.
На плоскости задан треугольник и еще множество точек. Необходимо найти такие две точки множества, что прямая, проходящая через эти две точки, пересекает треугольник, и при этом отрезок этой прямой, оказавшейся внутри треугольника, оказывается наибольшей длины. В качестве ответа хотелось бы видеть выделенные эти две точки, прямую, через них проходящую, и этот отрезок.
Множество точек на плоскости назовем дваждытреугольным, если каждая точка этого множества является вершиной хотя бы двух правильных треугольников, построенных по точкам множества. Определить, удовлетворяет ли заданное множество точек этому свойству.
Дано множество точек на плоскости. Определить среди них множество точек наибольшего размера такое, что каждая точка этого множества является вершиной равностороннего треугольника, вершины которого принадлежат этому множеству. В качестве ответа хотелось бы видеть все эти равносторонние треугольники.
Дано множество точек на плоскости. Определить среди них подмножество точек наибольшего размера такое, что каждая точка этого множества является вершиной хотя бы двух равносторонних треугольников, вершины которого принадлежат этому подмножеству. В качестве ответа хотелось бы видеть все эти равносторонние треугольники.
Дано множество точек на плоскости. Выберем из этого множества две точки и проведем через них прямую. Назовем дистанцией такую величину, что на расстоянии от прямой не меньше, чем дистанция лежит хотя бы половина оставшихся точек множества (кроме этих двух). Найти такую пару точек, у которой дистанция будет минимальна. В качестве ответа: выделить эти две точки, нарисовать проходящую через них прямую, выделить точки, лежащие на дистанции, нарисовать дистанцию (отрезок от одной из самых удаленных точек до прямой), а также "коридор" (две прямые, параллельные найденной прямой, находящиеся на найденной дистанции).
На плоскости задано множество прямоугольников. Найти такую пару пересекающихся прямоугольников, что длина отрезка, проведенного от одной точки пересечения этих двух прямоугольников до другой, максимальна. Если прямоугольники имеют более двух точек пересечения, выбирать среди них такую пару, расстояние между которыми максимально. В качестве ответа: выделить эту пару прямоугольников, нарисовать отрезок между найденными точками пересечения.
На плоскости задано множество "острых углов". Найти такие два "острых угла", что фигура, находящаяся "внутри" обоих "острых углов" замкнута и имеет максимальную площадь. Опция: искать только такие фигуры, все точки которых находятся внутри отображаемой на экране системы координат. В этом случае крайне желательно "залить цветом пространство фигуры". В качестве ответа: выделить найденные два "острых угла", выделить контур фигуры, которая ограничивает точки "внутри" обоих "острых углов", желательно выделить внутреннее пространство фигуры ("залить цветом").
На плоскости задано множество треугольников. Найти такие два треугольника, что площадь фигуры, находящейся внутри обоих треугольников, будет максимальна. В качестве ответа: выделить найденные два треугольника, выделить контур фигуры, находящейся внутри обоих треугольников, желательно "залить цветом" внутреннее пространство этой фигуры.
На плоскости задано множество прямоугольников. Найти такую пару пересекающихся прямоугольников, что площадь фигуры, находящейся внутри обоих прямоугольников, будет максимальна. В качестве ответа: выделить эту пару прямоугольников, выделить контур фигуры, находящейся внутри обоих треугольников, желательно "залить цветом" внутреннее пространство этой фигуры.
На плоскости задано множество окружностей и множество "острых углов". Найти такую пару "окружность - угол", что площадь фигуры, находящейся внутри найденной окружности и "острого угла" будет максимальной. В качестве ответа: выделить эту пару "окружность - угол", выделить контур фигуры, находящейся внутри окружности и "острого угла",
На плоскости задано множество прямоугольников и множество "острых углов". Найти такую пару "прямоугольник - угол", что площадь фигуры, находящейся внутри найденного прямоугольника и "острого угла" будет максимальной. В качестве ответа: выделить эту пару "прямоугольник - угол", выделить контур фигуры, находящейся внутри прямоугольника и "острого угла",
На плоскости задано множество треугольников и множество "острых углов". Найти такую пару "треугольник - угол", что площадь фигуры, находящейся внутри найденного треугольника и "острого угла" будет максимальной. В качестве ответа: выделить эту пару "треугольник - угол", выделить контур фигуры, находящейся внутри треугольника и "острого угла",
На плоскости задано множество "широких лучей". Найти такие два "широких луча", что фигура, находящаяся внутри этих двух "широких лучей" замкнута и имеет наибольшую площадь. В качестве ответа: выделить найденные два "широких луча", выделить контур фигуры, которая ограничивает точки внутри обоих "широких лучей", желательно выделить внутреннее пространство фигуры ("залить цветом").
На плоскости задано множество "широких лучей" и множество треугольников. Найти такую пару "широкий луч"-треугольник, что фигура, находящаяся внутри "широкого луча" и треугольника, имеет максимальную площадь. В качестве ответа: выделить найденные "широкий луч" и треугольник, выделить контур фигуры, которая ограничивает точки внутри найденного "широкого луча" и треугольника, желательно выделить внутреннее пространство фигуры ("залить цветом").
На плоскости задано множество "широких лучей" и множество окружностей. Найти такую пару "широкий луч"-окружность, что фигура, находящаяся внутри "широкого луча" и окружности, имеет максимальную площадь. В качестве ответа: выделить найденные "широкий луч" и окружность, выделить контур фигуры, которая ограничивает точки внутри найденного "широкого луча" и окружности, желательно выделить внутреннее пространство фигуры ("залить цветом").
На плоскости задано множество прямоугольников и множество окружностей. Найти такую пару прямоугольник-окружность, что фигура, находящаяся внутри прямоугольника и окружности, имеет максимальную площадь. В качестве ответа: выделить найденные прямоугольник и окружность, выделить контур фигуры, которая ограничивает точки внутри найденного прямоугольника и окружности, желательно выделить внутреннее пространство фигуры ("залить цветом").
На плоскости задано множество точек. Найти окружность, содержащую внутри себя хотя бы две точки множества, имеющую наибольшую плотность точек внутри себя (количество точек на единицу площади). В качестве ответа нарисовать найденную окружность и выделить все точки, находящиеся внутри нее.
На плоскости задано множество точек. Найти окружность наименьшей площади, внутри которой находятся все точки множества. Если таких окружностей несколько, найти любую. В качестве ответа нарисовать найденную окружность.
На плоскости задано два множества "параллельных" прямоугольников. Найти "разность" множеств. То есть, все такие точки плоскости, которые лежат внутри хотя бы одного прямоугольника первого множества, и не лежат ни в одном прямоугольнике второго множества. Отобразить найденное множество (желательно, "заливкой").
На плоскости задано два множества "параллельных" прямоугольников. Найти "пересечение" множеств. То есть, все такие точки плоскости, которые лежат внутри хотя бы одного прямоугольника первого множества, и внутри хотя бы одного прямоугольника второго множества. Отобразить найденное множество (желательно, "заливкой").
На плоскости задано множество точек. Найти такие две окружности, что их центры находятся в точках заданного множества, внутри этих окружностей находятся все точки заданного множества, и больший из двух радиусов минимален.
На плоскости задано множество точек. Найти такие две окружности, что их центры находятся в точках заданного множества, внутри этих окружностей находятся хотя бы половина из всех точек заданного множества, и максимальный из радиусов минимален.
На плоскости задано множество точек. Найти такие две окружности, что их центры находятся в точках заданного множества, внутри каждой из этих окружностей находятся хотя бы половина из всех точек заданного множества, и меньший из двух радиусов минимален.
На плоскости имеется прямая. Также имеется еще некоторое множество точек. По каждой паре точек этого множества строим прямые. Найти такие две пары точек, что построенные по ним две прямые пересекаются с первой прямой на минимальном расстоянии друг от друга. Выделить найденные точки, нарисовать прямые, построенные по ним. Выделить точки пересечения этих прямых с первой прямой. Выделить отрезок между этими точками пересечения. Дополнительная опция: искомые две пары точек не должны иметь общих точек.
На плоскости имеется окружность. Также имеется еще некоторое множество точек. По каждой паре точек этого множества строим прямые. Найти такие две пары точек, что построенные по ним две прямые пересекаются с окружностью на минимальном расстоянии друг от друга. Выделить найденные точки, нарисовать прямые, построенные по ним. Выделить точки пересечения этих прямых с окружностью. Выделить дугу между этими точками пересечения. Дополнительная опция: искомые две пары точек не должны иметь общих точек.
На плоскости задано множество точек. Найти из них такие 4 точки, что построенный по ним четырёхугольник не является самопересекающимся и имеет при этом максимальную площадь.
На плоскости задано множество точек. Найти из них такие 4 точки, что построенный по ним четырёххугольник не является самопересекающимся и содержит в себе максимальное количество точек множества.