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 xi1, yi1, xi2, yi2, trong đó (xi1, yi1) là tọa độ đỉnh trái dưới, còn (xi2, yi2) 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ố i1, i2, …, iK sao cho hình i1 nằm trong hình i2, hình i2 nằm trong hình i3, …, hình iK1 nằm trong hình iKK 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 xi1, yi1, xi2, yi2 có giá trị không vượt quá 30000.

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

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

Comments

Please read the guidelines before commenting.


There are no comments at the moment.