Задача I тура (автор В.В.Прохоров)

Пусть W-множество всех замкнутых односвязных ломанных на координатной плоскости xOy, удовлетворяющих условиям:

а) каждые два соседних звена ломанной взаимно перпендикулярны;

б) каждое звено ломанной параллельно одной из осей координат;

в) отсутствуют самопересечения или самокасания ломанной;

г) (x1, y1), ..., (хN, yN)- целочисленные координаты всех точек, где ломанная претерпевает излом (порядок нумерации произволен и неизвестен), N- количество изломов.

Требуется:

А. Написать по взможности оптимальные (по времени исполнения) программы с обоснованием алгоритмов), которые по задаваемым N и (x1, y1),..., (xN, yN) выдавали бы и отображали на экране монитора:

1) какую-либо ломанную из множества W;

2) ломанную из множества W, имеющую наибольшую длину, и значение этой длины;

3) ломанную из множества W, ограничивающую наибольшую площадь, и значение этой площади;

4) количество ломанных в множестве W.

Б.Решить задачу А, исключив пункт б) из определения W.

ПРИМЕЧАНИЕ. Односвязной называется ломанная, из любой точки которой можно попасть в любую другую ее точку, двигаясь по этой ломанной.

Задача II тура (авторы Е.В.Андреева и А.П.Марченко)[7, 92 г., 5-6]

В билете пассажира оказалось пробито отверстий больше, чем штырей в компостере. Пассажир утверждал, что пользовался только одним компостером, но случайно нажал его несколько раз. Контролеру требуется определить, могло ли быть получено заданное расположение отверстий одним и тем же компостером, если билет можно пробивать с обеих сторон неограниченное число раз и произвольно перемещать и поворачивать относительно компостера. Пробитые отверстия не выходят за пределы билета. В билете было пробито N (N<10) отверстий.

Требуется:

А. Для компостера с двумя штырями (S=2) составить программу, которая:

1) Определяет, можно ли получить заданным компостером требуемое расположение отверстий в билете. Если это возможно, то изображает вид билета после каждого нажатия компостера. В противном случае, выводит соответствующие сообщение.

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

3) При K=0 (см. пункт 2) находит компостер, с помощью которого можно пробить наибольшее количество из заданных отверстий.

4) Находит минимальное число нажатий, требуемое для пробивки заданной конфигурации отверстий, для каждого компостера из пункта 2.

Б. Решить задачу А для компостеров с числом штырей S (S>2).

Примечания. Все исходные данные - натуральные числа. Компостеры, дающие при однократном нажатии совпадающие конфигурации отверстий, считаются одинаковыми. Относительное расположение отверстий в билете и штырей в компостере вводятся либо с клавиатуры, либо из файла с именем COMP.DAT. Структура вводимой информации: {N, x1, y1, ..., xN, yN, S, u1, v1, ..., uS, vS}, где xi, yi- коодинаты отверстий в билете, ui, vi - координаты штырей в компостере. Нажатие компостера следует моделировать клавишей "Пробел". При выводе конфигурации на экран следует изображать координатную сетку. При этом программа должна осуществлять подходящее масштабирование.