文理学院程序设计在线练习


Do Use Search

Time Limit: 5 Second(s)    Memory Limit: 32 MB

Total Submission(s): 17   Accepted Submission(s): 7
Problem Description

Actually, Biving is a poor servant of Mr.Delle, and Mr.Delle always let Biving do some mission impossible. One day, Mr.Delle asks Biving to plant trees in his backyard as many as possible.
Mr.Delle’s backyard is rectangle shape land, whose size is W * H (W and H are so big that you can treat them as infinite). Biving has got N trees for planting. For the ith tree, it can be planted in RECTANGLE area (x1, y1, x2, y2) or (x3, y3, x4, y4) which hold x1<x2, y1<y2, x3<x4, y3<y4. So if Biving is decided to plant ith tree, she has to choose one of these two rectangle area as its GROUND.
Help Biving find the maximum number of trees she can plant satisfy that no two planted trees’ GROUND intersect with each other (But their GROUND can touch each other). For example, rectangle (1, 1, 5, 5) intersects with rectangle (2, 2, 6, 3), rectangle (1, 1, 5, 5) don’t intersect with rectangle (5, 2, 6, 3).

Input

The input contains several test cases (about 20).
For each case, the first line contains an integer N(1<=N<=50).Following N lines, each line contains 8 integers x1 y1 x2 y2(one rectangle area) x3 y3 x4 y4(another rectangle area) which describes two rectangles of ith tree’s possible planting area.(All coordinates are non-negative and less than 10000)

Output

For each test case, output the maximum trees Biving can plant.

Sample Input
2
0 0 1 1 0 0 1 1
0 0 2 2 0 0 3 3
2
0 0 1 1 1 1 2 2
0 0 2 2 0 1 1 2
3
0 0 1 1 2 3 4 5
1 2 3 4 5 6 7 8
5 5 6 6 7 7 8 8
Sample Output
1
2
3
Source

2013绍兴市赛