Kонкурс задач


Приложение "Информатика" открывает новую рубрику "Конкурс задач". Задачи предполагается публиковать один раз в месяц и один же раз в месяц проводить разбор задач предыдущей публикации и писем участников конкурса. Поскольку приложение выходит из печати с точностью до нескольких дней, последний срок, когда могут быть отправлены решения задач, будет указываться в каждой публикации с таким расчетом, чтобы время, отведенное на решение задач, составляло приблизительно полтора месяца. С каждым обзором будет публиковаться список участников, приславших верные решения. В конце года планируется подвести итоги конкурса и определить победителей. Победители конкурса награждаются как минимум бесплатной годовой подпиской на наше приложение (без учета почтовых расходов).

Конкурс рассчитан на учителей информатики и старшеклассников. Решения могут присылать как индивидуальные, так и коллективные участники (кружки, дома творчества и т. д.).

В письмах указывайте, пожалуйста, обратный адрес для переписки с вами.

Одной из целей конкурса является оказание методической помощи учителям, ведущим кружковые и факультативные занятия. Многие из публикуемых задач могут быть использованы для проведения таких занятий, при подготовке к олимпиадам и для проведения олимпиад разного уровня.

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

В присылаемых решениях алгоритмы должны быть оформлены в виде программ или их фрагментов на одном из общеизвестных языков программирования либо в записи в содержательных обозначениях. В первом случае требуются комментарии, проясняющие предложенный алгоритм: семантика используемых переменных, входных параметров подпрограмм и возвращаемых ими значений и т. п. Обязательным являются описание идеи алгоритма и проведение необходимых обоснований. В качестве примера приведем разбор одной из задач настоящей публикации.

Редакция приглашает авторов задач к активному сотрудничеству.

Желаем успехов в нашем конкурсе!


УСЛОВИЯ ЗАДАЧ

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, а затем решить, какие точки стоит рассматривать.

Утверждение, выделенное курсивом, можно считать новой задачей (с тем же номером).