Задача №112980. domiki
Страну «Флатландия» населяют плоские жители, которые живут в плоских домиках на координатной плоскости. Все домики имеют форму прямоугольников. Все стороны прямоугольников параллельны осям координат, все вершины имеют целочисленные положительные координаты. Стороны различных прямоугольников не пересекаются, но могут иметь общую сторону или общую часть стороны, например, соприкасаться вершинами. Необходимо определить, сколько домиков видно полностью и частично, если смотреть на них из начала координат (точка с координатами 0, 0 ) Отрезок AB , где точки A и B принадлежат одной стороне прямоугольника (домика), считается видимым из точки O , если внутренние точки треугольника OAB не имеют общих точек с каким-либо другим прямоугольником (домиком). Сторона домика видна, если виден отрезок AB , где A и B — начало и конец данной стороны домика. Домик виден полностью, если полностью видна какая-либо его сторона. Домик виден частично, если виден отрезок AB на какой-либо стороне домика, точки A и B различны. Требуется написать программу, которая по полученной информации установит:
- Сколько домиков видно полностью?
- Сколько домиков видно частично?
Первая строка входного файла содержит число P ( 1 или 2 ) — номер пункта задачи, ответ на который требуется получить. Вторая строка файла содержит число N ( 1 ≤ N ≤ 1000 ) — количество домиков. Каждая из последующих N строк содержит четыре числа x 1 , y 1 , x 2 , y 2 , разделенные пробелом, — координаты нижнего левого ( x 1 , y 1 ) и верхнего правого ( x 2 , y 2 ) угла домика в форме прямоугольника. Все координаты натуральные и не превышают 30 000 .
В выходной файл выводится количество видимых домиков (если P = 1 , то — количество полностью видимых домиков, если P = 2 , то — количество частично видимых домиков).
Примеры соответствуют рисунку
Потестовая.
1 5 1 2 2 3 3 1 4 2 2 4 4 6 3 7 5 8 6 3 7 7
2
2 5 1 2 2 3 3 1 4 2 2 4 4 6 3 7 5 8 6 3 7 7
3