Задача №1885. Прямоугольники
Вася очень любит головоломки, в которых необходимо посчитать количество прямоугольников на большой картинке с горизонтальными и вертикальными отрезками. Сегодня он нарисовал прямоугольник \(m\times n\) на прямоугольной решетке на своем ноутбуке, несколько таких отрезков внутри и предложил своему брату Саше решить головоломку. Но Саша не хочет проводить время, считая прямоугольники, которых так много, поэтому он решил использовать свой компьютер для этого. Он попросил вас написать программу, которая найдет количество прямоугольников на прямоугольной решетке с несколькими вертикальными и горизонтальными отрезками на ней.
Входной файл состоит из нескольких наборов тестов. Каждый тест начинается со значений \(m\) и \(n\). В следующей строке находится единственное число \(k\) — количество нарисованных отрезков. Далее идут описания отрезков. Каждый отрезок описывается четырьмя целыми числами \(x_1,y_1,x_2,y_2\), где либо \(x_1=x_2\), либо \(y_1=y_2\). Все \(x\) из диапазона от \(0\) до \(m\), а \(y\) — от \(0\) до \(n\). Значения \(n\) и \(m\) не превосходят 100.
Входной файл заканчивается строкой, состоящей из двух нулей.
Саша довольно неаккуратный. Он мог поместить один и тот же отрезок несколько раз во входной файл. Также он мог разбить отрезок на несколько частей, возможно перекрывающихся.
Для каждого теста из входного набора необходимо вывести количество прямоугольников на решетке, в соответствии с форматом, приведенным в примере.
2 2 2 0 1 2 1 1 1 1 2 2 2 1 0 1 1 1 0 0
Grid 1: The number of rectangles is 5. Grid 2: The number of rectangles is 1.