Dãy hình chữ nhật lồng nhau

View as PDF

Submit solution

Points: 200.00 (partial)
Time limit: 1.0s
Memory limit: 1G
Input: stdin
Output: stdout

Author:
Problem type
Allowed languages
C, C++, GAS64, Pascal, Perl, PHP, Python, Sed, TCL, Text

Trên mặt phẳng tọa độ cho ~N~ hình chữ nhật với các cạnh song song với hệ trục tọa độ, các hình chữ nhật được đánh số từ ~1~ tới ~N~. Hình chữ nhật thứ ~i~ được cho bởi 4 số nguyên dương ~x_{i1}~, ~y_{i1}~, ~x_{i2}~, ~y_{i2}~, trong đó (~x_{i1}~, ~y_{i1}~) là tọa độ đỉnh trái dưới, còn (~x_{i2}~, ~y_{i2}~) là tọa độ đỉnh phải trên. Ta nói rằng hình chữ nhật thứ ~i~ nằm trong hình chữ nhật thứ ~j~ nếu trên mặt phẳng tọa độ, mọi điểm của hình chữ nhật ~i~ đều thuộc hình chữ nhật ~j~.

Yêu cầu: Với ~N~ hình chữ nhật cho trước, hãy tìm ~K~ hình chữ nhật với chỉ số ~i_1~, ~i_2~, …, ~i_K~ sao cho hình ~i_1~ nằm trong hình ~i_2~, hình ~i_2~ nằm trong hình ~i_3~, …, hình ~i_{K-1}~ nằm trong hình ~i_K~ và ~K~ là lớn nhất.

Dữ liệu:

  • Dòng đầu tiên chứa số nguyên dương ~N~ (~1 <= N <= 100~).
  • ~N~ dòng tiếp theo, dòng thứ ~i~ chứa 4 số nguyên dương ~x_{i1}~, ~y_{i1}~, ~x_{i2}~, ~y_{i2}~ có giá trị không vượt quá ~30000~.

Kết quả: Ghi ra số ~K~ tìm được.

Ví dụ:
INPUT
3
1 1 7 4
3 1 6 6
2 2 5 4
OUTPUT
2

Comments

Please read the guidelines before commenting.


There are no comments at the moment.