Задача №1255. Плакат
Министерство образования Флатландии недавно приняло решение о начале реализации проекта по использованию социальной рекламы для повышения грамотности населения. Социальная реклама будет размещаться в виде видеороликов на телевидении, плакатов на улицах городов, а также в журналах и газетах.
Один из плакатов, подготовленных в рамках этого проекта, выполнен в весьма абстрактном стиле. Плакат имеет форму прямоугольника высотой h и шириной w, который изначально полностью покрашен в белый цвет. На плакате изображены несколько прямоугольников разных цветов.
Для того, чтобы напечатать этот плакат службе снабжения министерства образования необходимо выяснить, сколько краски какого цвета для этого требуется.
Так как во Флатландии повсеместно внедрены информационные технологии, то подготовка плаката велась с помощью специальной программы. В этой программе (как и во многих других) цвета представляются в так называемом RGB-формате. Это означает, что цвет кодируется тремя целыми числами, каждое из которых находится в пределах от 0 до 31 (обычно используются значения от 0 до 255, но оборудование, используемое для печати, обладает ограниченными возможностями цветопередачи). Эти числа обозначают интенсивность красной, зеленой и синей компонент цвета (0 соответствует отсутствию соответствующей компоненты, а 31 — ее максимальной интенсивности).
Таким образом, черный цвет кодируется как (0; 0; 0), а белый — как (31; 31; 31).
Цвета различных областей плаката определяются следующим образом. Изначально весь плакат заполняется белым цветом (таким образом, исходно все точки имеют цвет (31; 31; 31)), после чего выполняется рисование прямоугольников, заданных в описании плаката. При рисовании прямоугольника цветом, который кодируется как (r; g; b), новые цвета точек, находящихся внутри этого прямоугольника, определяются так: если до рисования точка имела цвет (r1; g1; b1), то после того, как прямоугольник будет нарисован, ее цвет будет равен ((r1+r) mod 32; (g1+g) mod 32; (b1+b) mod 32).
Например, на рисунке приведен плакат, который получается из белого листа размера 10 # 10 изображением двух прямоугольников: цвета (12; 0; 12) с координатами левого нижнего угла (0; 0) и правого верхнего (5; 5), а затем цвета (0; 12; 0) с координатами левого нижнего угла (4; 4) и правого верхнего (6; 6).
Таким образом, цвет каждой точки зависит от того, в каких прямоугольниках она лежит, и от того, каковы их цвета. Ваша задача состоит в том, чтобы написать программу, которая по описанию плаката вычислит число различных цветов, которые на нем присутствуют, а также площадь, закрашенную каждым из этих цветов.
Первая строка входного файла содержит число n прямоугольников, изображенных на плакате (0 ≤ n ≤ 1500). Вторая строка входного файла содержит два целых числа w и h — соответственно, ширину и высоту плаката (1 ≤ w, h ≤ 109). Каждая из последующих n строк описывает один из прямоугольников, изображенных на плакате, и содержит семь целых чисел: x1, y1, x2, y2, r, g, b. Первые два из них — координаты левого нижнего угла прямоугольника, третье и четвертое — координаты правого верхнего угла. Для этих чисел выполняются неравенства 0 ≤ x1 < x2 ≤ w, 0 ≤ y1 < y2 ≤ h. Пятое, шестое и седьмое числа задают цвет прямоугольника — они равны, соответственно, красной, зеленой и синей компонентам цвета (0 ≤ r, g, b ≤ 31).
Система координат введена таким образом, что левый нижний угол плаката имеет координаты (0; 0), а правый верхний — (w, h).
В первой строке выходного файла выведите число k различных цветов, которые необходимы для печати плаката. Далее выведите k строк — каждая из них должна содержать четыре числа — первые три из них должны описывать цвет (первое из них должно быть равно значению красной компоненты, второй — зеленой, а третье — синей), а четвертое должно быть равно площади части плаката, которая будет закрашена этим цветом.
2 10 10 0 0 5 5 12 0 12 4 4 6 6 0 12 0
4 11 11 11 1 11 31 11 24 31 11 31 3 31 31 31 72
0 7 8
1 31 31 31 56
2 10 10 0 0 5 5 20 21 22 4 4 6 6 15 16 17
4 2 4 6 1 14 15 16 3 19 20 21 24 31 31 31 72