XI городская олимпиада школьников
Санкт-Петербурга по информатике

1996 год

Практический тур

Задачи

Комментарий ко всем задачам

ЗЛ - замкнутая ломаная без самопересечений и самокасаний, звенья которой параллельны осям координат. Ломаная задается перечислением координат вершин в порядке обхода по часовой стрелке, первая и последняя вершины совпадают. Координаты вершин - целые числа. Ломаная содержит не более 100 звеньев. Ломаная не содержит последовательных параллельных звеньев.

Задача A. Замкнутая ломаная 1

Задана ЗЛ A и целое число K. Требуется найти ЗЛ B, имеющую минимально возможную площадь при одновременном выполнении следующих условий:

Формат входных данных

Во входном файле INPUT.TXT содержится описание ломаной и число K.

Формат выходных данных

Результат работы вывести одновременно в файл OUTPUT.TXT и на графический экран. В выходном файле ломная задается также, как во входных данных. На графическом экране изобразите ломную A белым цветом, а ломную B - зеленым. Ваша программа должна выполнить подходящее масштабирование и центровку изображения.

Пример

input.txtoutput.txt
10 0 10 20 30 20 30 10 40 10 40 0 10 0
13
-3 -13 -3 33 53 33 -3 -13

Задача B. Замкнутая ломаная 2

Задана ЗЛ A и целое число K. Требуется найти ЗЛ B, имеющую минимально возможную площадь при одновременном выполнении следующих условий:

Формат входных данных

Во входном файле INPUT.TXT содержится описание ломаной и число K.

Формат выходных данных

Результат работы вывести одновременно в файл OUTPUT.TXT и на графический экран. В выходном файле ломная задается также, как во входных данных. На графическом экране изобразите ломную A белым цветом, а ломную B - зеленым. Ваша программа должна выполнить подходящее масштабирование и центровку изображения.

Пример

input.txtoutput.txt
10 0 10 20 30 20 30 10 40 10 40 0 10 0
5
15 5 15 15 25 15 25 5 15 05 

Задача C. Замкнутая ломаная 3

Задана ЗЛ A и точка с целочисленными координатами (x, y), не лежащая на ломаной A. В точке находится источник света, который освещает непосредственно видимые из него участки ломаной A. Требуется найти освещенные и неосещенные участки ломаной A. Результат работы вывести одновременно в файл OUTPUT.TXT и на графический экран. В файл OUTPUT.TXT вывести только суммарную длину всех освещенных участков. На графическом экране изобразите ломаную A и точку (x, y). Освещенные участки ломаной рисуются белым цветом, а неосвещенные - серым. Ваша программа должна выполнить подходящее масштабирование и центровку изображения.

Формат входных данных

Во входном файле INPUT.TXT содержится описание ломаной и число K.

Формат выходных данных

Результат работы вывести одновременно в файл OUTPUT.TXT и на графический экран. В выходном файле ломная задается также, как во входных данных. На графическом экране изобразите ломную A белым цветом, а ломную B - зеленым. Ваша программа должна выполнить подходящее масштабирование и центровку изображения.

Пример

input.txtoutput.txt
10 0 10 20 30 20 30 10 40 10 40 0 10 0
35 5
9