RECT1 - Các hình chữ nhật
Giới hạn- Thời gian: 0.077s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
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
- Người up: dtmp