Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

RECT1 - Các hình chữ nhật

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/rect1


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, ymax), (xmax, ymax)] hoặc đoạn [(xmax, 0), (xmax, ymax)].
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 xmax, ymax (0 < xmax, ymax < 10^9) và N (1 <= N <= 10000).
- Mỗi dòng trong N dòng tiếp theo chứa 4 số nguyên: x1, y1, x2, y2. (x1, y1) là tọa độ đỉnh trái dưới, (x2, y2) 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.

Example

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

Output:
5

Được gửi lên bởi:Nguyen Dinh Tu
Ngày:2006-10-14
Thời gian chạy:0.100s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET

hide comments
2017-09-27 11:10:33
P/S cho mình xin 1 test mình sai được không -.- , xử lý hình học khó chịu quá
2014-07-07 11:21:34 a;slkfjasl;fkj
các tọa độ của hcn cũng phải >=0 chứ nhỉ, thấy chắc chữ nguyên?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.