[BOJ 9891] Rect
View as PDFA 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