Приложение "Информатика" открывает новую рубрику "Конкурс задач". Задачи предполагается публиковать один раз в месяц и один же раз в месяц проводить разбор задач предыдущей публикации и писем участников конкурса. Поскольку приложение выходит из печати с точностью до нескольких дней, последний срок, когда могут быть отправлены решения задач, будет указываться в каждой публикации с таким расчетом, чтобы время, отведенное на решение задач, составляло приблизительно полтора месяца. С каждым обзором будет публиковаться список участников, приславших верные решения. В конце года планируется подвести итоги конкурса и определить победителей. Победители конкурса награждаются как минимум бесплатной годовой подпиской на наше приложение (без учета почтовых расходов).
Конкурс рассчитан на учителей информатики и старшеклассников. Решения могут присылать как индивидуальные, так и коллективные участники (кружки, дома творчества и т. д.).
В письмах указывайте, пожалуйста, обратный адрес для переписки с вами.
Одной из целей конкурса является оказание методической помощи учителям, ведущим кружковые и факультативные занятия. Многие из публикуемых задач могут быть использованы для проведения таких занятий, при подготовке к олимпиадам и для проведения олимпиад разного уровня.
Предлагаемые задачи будут носить преимущественно алгоритмический характер, т. е. для их решения потребуется не столько техника программирования, сколько умение придумывать алгоритмы.
В присылаемых решениях алгоритмы должны быть оформлены в виде программ или их фрагментов на одном из общеизвестных языков программирования либо в записи в содержательных обозначениях. В первом случае требуются комментарии, проясняющие предложенный алгоритм: семантика используемых переменных, входных параметров подпрограмм и возвращаемых ими значений и т. п. Обязательным являются описание идеи алгоритма и проведение необходимых обоснований. В качестве примера приведем разбор одной из задач настоящей публикации.
Редакция приглашает авторов задач к активному сотрудничеству.
Желаем успехов в нашем конкурсе!
1. Два отрезка заданы координатами своих концов. Определить, пересекаются ли они во внутренних точках.
2. Выпуклый n-угольник задан координатами своих вершин. Определить, является ли точка М с координатами (a, b) внутренней.
3. На плоскости задано конечное множество точек М. Его выпуклой оболочкой называется наименьшее подмножество этих точек, такое, что выпуклый многоугольник с вершинами в этих точках содержит М. Для заданного множества построить выпуклую оболочку.
4*. Соединить конечное множество точек на плоскости замкнутой ломаной линией без самопересечений с вершинами в этих точках.
5*. На плоскости имеется n белых и n черных точек, причем никакие три из этих 2n точек не лежат на одной прямой. Соединить их n отрезками так, чтобы каждая белая была соединена с одной черной и наоборот и отрезки не пересекались. Всегда ли это возможно?
6**. На плоскости заданы n точек, никакие три из которых не лежат на одной прямой. Найти круг наименьшего радиуса, содержащий эти точки (указать радиус и координаты центра, граница круга ему принадлежит).
Замечание: все точки в предложенных задачах лежат на плоскости и задаются своими координатами. Ошибками округления пренебречь.
ПРИМЕР РЕШЕНИЯ ЗАДАЧИ
В качестве примера разберем решение самой трудной последней задачи. Приведенный ниже алгоритм прост: нужно перебрать все тройки точек и решить задачу для каждой из них, а затем выбрать самый большой круг. Однако обоснование (без которого додуматься до идеи алгоритма невозможно) достаточно сложно.
1. Пусть n=3. Тогда искомый круг - или описанный около треугольника с вершинами в этих точках, если он остроугольный, или построенный на большей стороне, как на диаметре, - в противном случае (докажите!)
2. Для дальнейшего нам понадобится частный случай теоремы Хелли на плоскости. Поскольку доказательство для частного случая ничем не отличается от общего, приведем формулировку и доказательство теоремы полностью.
Определение. Множество точек называется выпуклым, если с любыми двумя точками оно содержит и отрезок, их соединяющий.
Теорема Хелли на плоскости. Если среди n>3 выпуклых множеств любые три пересекаются, то и все они содержат общую точку.
Доказательство - индукцией по n.
База индукции: Пусть n=4 и М1, М2, М3, М4 - данные множества. Пусть А принадлежит множествам с номерами 1, 2, 3; В - множествам с номерами 2, 3, 4; С - 3, 4, 1 и D - 4, 1, 2. Тогда если АВСD - выпуклый четырехугольник, то его диагонали пересекаются, и точка пересечения - искомая.
Если же это не так, то одна из диагоналей, пусть АС, не лежит внутри четырехугольника. Но тогда либо В, либо D лежит внутри треугольника, образованного тремя другими точками. Пусть эта точка D. Тогда все три вершины треугольника принадлежат М3, поэтому и весь треугольник содержится в М3, следовательно, точка D - искомая. (Все ли случаи мы разобрали?).
Индуктивный переход. Пусть утверждение верно для любых n множеств и рассмотрим n+1 таких множеств, М1, М2, ..., Мn, Mn+1.
Заменим два последних на их пересечение L, которое, очевидно, тоже выпуклое. Если любые три из n+1 множеств пересекаются, то это верно и для нового набора. Действительно, если ни одно из этих множеств не совпадает с L, то они пересекаются по условию, а если совпадает, то это следует из доказательства базы индукции. Следовательно, и т.д.
3. Окончание обоснования алгоритма. Пусть А, В и С - точки, для которых наименьший содержащий их круг - самый большой, R - его радиус. Построим в каждой точке данного множества круг радиуса R. Тогда любые три из них пересекаются: по крайней мере содержат центр того круга, который был построен для их центров. По теореме Хелли все круги содержат общую точку К. Тогда круг радиуса R с центром в точке К содержит все точки данного множества, в частности А, В и С, а потому совпадает с наименьшим кругом, построенным для А, В и С.
Описание алгоритма
Будем считать, что точки множества заданы массивом структур (записей), состоящих из координат точек с индексами от 0 до n-1. (Если читатель незнаком с таким типом данных, он может считать, что точки заданы двумя массивами - координатами по осям х и у.)
Пусть m, n и l - переменные указанного типа для запоминания предыдущей тройки точек, соответствующих наибольшему кругу, rn - переменная с текущим радиусом круга, r - c наибольшим.
алгоритм
инициализация: m к-0, n к-0, l к-0, r к-0
цикл по i от 0 до n-3
цикл по j от i+1 до n-2
цикл по k от j+1 до n-1
тело цикла:
rn к-радиус (i, j, k)
если r < rn, то r к-rn,
m к-i, n-к j, l к-k
конец если
конец цикла по k
конец цикла по j
конец цикла по i
(x, y) к центр (m,n,e)
конец
II. Центр (p, q, s)
Входные данные: индексы точек.
Выходные данные: координаты центра искомого круга.
Описание работы: центр определяется либо как в п.2 предыдущей функции, либо составляются уравнения прямых, проходящих через середины двух отрезков и им ортогональных, и ищется решение системы.
Обсуждение
Наш алгоритм перебирает все различные тройки точек, количество которых (n(n-1)(n-2))/6, поэтому число действий, не превосходит kn3, где k не зависит от n. На самом деле его можно сделать линейным, т. е. с числом действий не превосходящих kn. Для этого сначала следует решить задачу 3, а затем решить, какие точки стоит рассматривать.
Утверждение, выделенное курсивом, можно считать новой задачей (с тем же номером).