Город имеет форму круга радиуса R с центром в точке (0,0).
Сеть метро состоит из N линий метро (часть линий или все проходят через город).
Линия метро - ломаная из отрезков прямых, вершины которых имеют целочисленные координаты. Линия метро не имеет самопересечений и может быть замкнутой. Во всех точках с целочисленными координатами, через которые проходят линии метро расположены станции метро .
Для каждой точки с целочисленными координатами определим параметр вес вершины. Вес вершины — это количество станций метро, расстояние до которых не более 1 (длины клетки).
Город разбит на кварталы.
Квартал — это единичная клетка с целочисленными координатами вершин, хотя бы одна из которых находящаяся строго внутри города.
Для каждого квартала определим параметр
доступность. Доступность квартала равна сумме весов вершин квартала (вершина квартала может быть вне города)
Найдите значение "доступности" для каждого квартала. Для каждой полученной "доступности" определите число кварталов, имеющих эту доступность.
Входные данные
В первой строке заданы значения R, N (4<R<201, 0<N<1001)
В следующих N строках заданы описания линий метро.
Каждая линия описывается следующим образом:
первое число в строке M равно количеству вершин ломаной, далее даны координаты вершин (по два числа на вершину).
Замкнутые ломаные определяются тем, что координаты начальной и конечной вершины совпадают.
Выходные данные
В первой строке выведите число K - количество различных значений "доступности" (включая нулевую).
В следующих K строках выведите по два числа - значение "доступности" и число кварталов, имеющих такое значение "доступности"
Примеры:
| № |
Входные данные |
Выходные данные |
Примечание |
| 1 |
5 3
6 2 -4 -2 -4 -4 0 0 4 4 0 2 -4
4 -6 3 0 -1 2 -1 5 -4
3 5 4 0 -1 -6 -4 |
14
0 3
1 1
2 4
3 8
4 10
5 9
6 12
7 11
8 13
9 5
10 6
11 3
12 2
13 1 |
Город (рис. 1,2) расположен в круге радиуса 5 с центром в точке (0,0).
Сеть метро состоит из 6 линий метро (2 радиальных, 1 кольцевая):
6 2 -4 -2 -4 -4 0 0 4 4 0 2 -4 - кольцевая линия из 5 звеньев, 16 станций
4 -6 3 0 -1 2 -1 5 -4 - радиальная линия из 3 звеньев, 8 станций
3 5 4 0 -1 -6 -4 - радиальная линия из 2 звеньев, 9 станций
Есть три пересадки ( в вершинах (-3,1), (0,-1), (3,-2))
На рис.1 отмечены вершины, которые не являются станциями и
имеют не нулевой вес (треугольник - вес 1, крестик - вес 2, ромб - вес 3)
На рис.2 для всех городских кварталов указано значение параметра
доступности квартала. |