Các hình chữ nhật

Xem dạng PDF

Gửi bài giải


Điểm: 0,65 (OI)
Giới hạn thời gian: 0.38s
Giới hạn bộ nhớ: 512M
Input: stdin
Output: stdout

Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Cho ~N~ hình chữ nhật trên mặt phẳng. Các cạnh hình chữ nhật song song với các trục tọa độ. Những hình chữ nhật này có thể gối lên nhau, trùng hoặc là bên trong nhau. Đỉnh của chúng có tọa độ nguyên, hoành độ ~x~ không vượt quá ~xmax~ và tung độ ~y~ không vượt quá ~ymax~.

Một đoạn thẳng có một đầu là điểm ~A~ (~0~, ~0~) và đầu kia là điểm ~B~. Điểm ~B~ thỏa mãn các điều kiện sau:

  • Các tọa độ của ~B~ là những số nguyên.
  • Điểm ~B~ thuộc đoạn ~[(0, y_{max})~, ~(x_{max}, y_{max})]~ hoặc đoạn ~[(x_{max}, 0)~, ~(x_{max}, y_{max})]~.

Viết chương trình tìm một điểm ~B~ sao cho đoạn ~AB~ cắt qua nhiều hình chữ nhật nhất. (~AB~ cắt ~1~ hình chữ nhật khi chúng có ít nhất ~1~ điểm chung với nhau).

Input

  • Dòng đầu chứa ~3~ số nguyên ~x_{max}, y_{max}~ ~(0 < x_{max}, y_{max} < 10^{9})~ và ~N~ (~1 \le N \le 10000~).
  • Mỗi dòng trong ~N~ dòng tiếp theo chứa ~4~ số nguyên: ~x_1~, ~y_1~, ~x_2~, ~y_2~. ~(x_1~, ~y_1)~ là tọa độ đỉnh trái dưới, ~(x_2~, ~y_2)~ là tọa độ đỉnh phải trên của hình chữ nhật tương ứng.

Output

Dòng duy nhất ghi số lượng lớn nhất các hình chữ nhật cắt được.

Sample Input

22 14 8
1 8 7 11
18 10 20 12
17 1 19 7
12 2 16 3
16 7 19 9
8 4 12 11
7 4 9 6
10 5 11 6

Sample Output

5

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.