0053. Многоугольник

Имя входного файла: input.txt
Имя выходного файла: output.txt
Ограничение по времени: 1 s
Ограничение по памяти: 64 megabytes

Хорошо известно, что никакой графический редактор (за редким исключением) не обходится без возможности манипуляции с графическими примитивами, такими , например, как произвольный многоугольник. Ваша задача √ реализовать закраску подобного произволдьного многоугольника (невырожденного и без самопересечений, однако его ребра могут быть вырожденными) и вывести в кодированном виде результат в файл. В качестве алгоритма кодирования используется самая простая реализация алгоритма RLE, в котором растр кодируется последовательностью из 2-х чисел: первое-цвет, второе √ количество его повторений в растре. Для упрощения задачи все грани заданного многоугольника будут параллельны осям координат, для закраски многоугольника будет использоваться цвет с кодом 1, для фона 0. Многоугольник задается координатами своих вершин в порядке обхода.

Формат входного файла

Количество заданных вершин N (4 ≤ N ≤ 1000); координаты вершин многоугольника √ целые числа, находящиеся в интервалах [-640;639] и [-512;511] для x и y соответственно.

Формат выходного файла

Ваша задача √ сформировать кодированный растр размером 1280*1024 pix и вывести его в файл так, чтобы каждая новая строка растра занимала новую строку в файле. При этом верхняя строка файла соответствует координате (√512) по оси ординат. А крайний левый символ каждой строки соответствует координате (√640) по оси абсцисс. При заполнении точек цветом следует отметить, что точка ассоциируется со своим левым верхним углом, те четырехугольник с координатами (1,1); (1,-1); (-1,-1); (-1,1) будет закрашен следующим образом: (Темный квадрат соответствует пикселу с координатами (0,0)).

Пример:

input.txtoutput.txt
4 1 1 1 -1 -1 -1 -1 1 0 1280 (повторено 510 раз) 0 639 1 2 0 639 0 639 1 2 0 639 0 1280 (повторено 512 раз)


Источник: Petrozavodsk training camp, Summer 2002. Magloy's contest :-)
Автор: Magloy (Alexander Korol, Denis Vlasov, Roman Soshkin)

Обсудить       Отправить решение



Версия для печати