Задача Logo
Известный участникам олимпиады оператор Kife:( объявил конкурс на новый логотип компании. Герой олимпиад Вася Пупкин задался целью выиграть этот конкурс. Для этого он нарисовал очень креативный логотип: сначала начертил квадратную сетку NхN ячеек, далее нарисовал на этой сетке K отрезков с концами в центрах ячеек. Он решил закрасить все ячейки сетки, которые пересекает хотя бы один отрезок. Вот тут-то и возникла проблема: Вася не знает, сколько краски ему понадобится. Помогите Васе! Напишите программу, которая посчитает количество ячеек, которые нужно закрашивать.
Технические условия. Программа Logo читает с клавиатуры числа N и K (1<=N<=1000, 0<=K<=1000), а затем K групп по 4 целых числа - координаты ячеек-концов отрезков (1<=Xi1,Yi1,Xi2,Yi2<=N). Программа выводит на экран искомое число ячеек, которые нужно закрасить.
Пример
|
Вввод 10 3 3 7 4 2 2 4 5 5 2 6 6 8 Вывод 15 |
 |