[BOJ 9891] Rect

View as PDF

Submit solution

Points: 1
Time limit: 2.0s
Memory limit: 512M

Problem types
Allowed languages
Assembly, Awk, C, C++, Java, Pascal, Perl, Python, Sed, Text

A rectangle is axis-parallel if its top and bottom sides are parallel to the x-axis and its left and right sides are parallel to the y-axis. From now on by a rectangle we mean an axis-parallel rectangle.</p>

A rectangle will be specified by a 4-tuple (x1, y1, x2, y2) in which (x1, y1) is the bottom-left corner and (x2, y2) is the top-right corner of the rectangle. We will also say the rectangle (x1, y1, x2, y2) is a (x2 − x1) × (y2 − y1) rectangle.

Two rectangles are incomparable if neither will fit inside the other possibly with translation and 90 rotation; otherwise, the two rectangles are comparable. Given a list of rectangles, you are to output the number of pairs of incomparable rectangles.

입력 형식

The first input line contains an integer which is the number of rectangles n (where 0 ≤ n ≤ 10000). Each of the next n lines describes a rectangle and contains four integers x1, y1, x2, y2, a space separates two adjacent integers. Recall that coordinates (x1, y1), (x2, y2) specify respectively the bottom-left and top-right corner of the rectangle. All coordinate values are in the range of 0 to 10,000; that is, 0 ≤ x1 ≤ 10000, 0 ≤ y1 ≤ 10000, 0 ≤ x2 ≤ 10000, 0 ≤ y2 ≤ 10000.

출력 형식

The output file contains a single integer which is the number of pairs of incomparable rectangles.

예제 입력 1

3
0 0 2 2
0 0 3 1
1 1 3 4

예제 출력 1

1

예제 입력 2

4
3 3 4 6
1 2 4 3
5 6 7 8
10 10 12 12

예제 출력 2

4

Comments

There are no comments at the moment.