Untidy Desktops
InterviewTime limit7sMemory limit128 MB
Given n axis-aligned rectangles, count how many overlap at least one other rectangle, boundaries included.
- Level
Easy3 of 10
- Topics
- Geometry, Brute force
- Solved
- No attempts yet
Problem
Many companies are moving toward “paperless offices” in an attempt to increase productivity. Unfortunately, people who are disorganized with paper stay disorganized without it! Instead of piles of paper scattered across a desk, their screens are covered with windows overlapping and hiding one another. For these people, finding the right window on the screen is just as hard as finding the right sheet of paper on the desk.
In this problem you are given the positions and sizes of windows on a computer desktop (). Measure how untidy the desktop is by counting how many windows overlap at least one other window. Two windows overlap if at least one pixel belongs to both of them (their boundaries included).
Input
The input consists of several test cases. Each case begins with a line containing a single integer , followed by lines describing one window each in the form
r c w h
where , are the row and column coordinates of the window's upper-left corner and , are its width and height. That is, the window covers every pixel in rows through and columns through . The upper-left corner of the desktop is at coordinates , the screen has rows and columns, and every window lies completely within the screen boundary. A line with terminates the input.
Output
For each test case, print on a single line the number of windows that overlap at least one other window.