Under construction

Still being built. Things may change

Untidy Desktops

Interview

Time limit7sMemory limit128 MB

Summary
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 nn windows on a computer desktop (1≤n≤501 \le n \le 50). 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 nn, followed by nn lines describing one window each in the form

r c w h

where rr, cc are the row and column coordinates of the window's upper-left corner and ww, hh are its width and height. That is, the window covers every pixel in rows rr through r+h−1r+h-1 and columns cc through c+w−1c+w-1. The upper-left corner of the desktop is at coordinates (0,0)(0, 0), the screen has 10241024 rows and 12801280 columns, and every window lies completely within the screen boundary. A line with n=0n = 0 terminates the input.

Output

For each test case, print on a single line the number of windows that overlap at least one other window.

Examples1

  1. Example 1

    Input
    3
    0 0 20 20
    20 20 20 20
    40 40 20 20
    5
    0 0 20 20
    18 18 20 20
    40 40 20 20
    5 10 4 2
    100 100 40 40
    0
    
    Expected output
    0
    3