提示: 欢迎访问OurACM平台。因与高数考试冲突,校赛改为5月6日13:00-17:00
Problem 1030 Rectangles

Accept: 211    Submit: 632
Time Limit: 2000 mSec    Memory Limit : 32768 KB

Problem Description

specialist in VLSI design testing must decide if there are some components that cover each other for a given design. A component is represented as a rectangle. Assume that each rectangle is rectilinearly oriented (sides parallel to the x and y axis), so that the representation of a rectangle consists of its minimum and maximum x and y coordinates.

Write a program that counts the rectangles that are entirely covered by another rectangle.

The input contains the text description of several sets of rectangles. The specification of a set consists of the number of rectangles in the set and the list of rectangles given by the minimum and maximum x and y coordinates separated by white spaces, in the format:

nr_rectangles
xmin1 xmax1 ymin1 ymax1
xmin2 xmax2 ymin2 ymax2

xminn xmaxn yminn ymaxn

The output should be printed on the standard output. For each given input data set, print one integer number in a single line that gives the result (the number of rectangles that are covered). An example is given in Figure 1.


Sample Input

3 100 101 100 101 0 3 0 101 20 40 10 400 4 10 20 10 20 10 20 10 20 10 20 10 20 10 20 10 20

Sample Output

0 4

Source

Southeastern European Regional Programming Contest 2000 F

Submit  Back  Status  Discuss