Cắt bánh
Đề bài
Mô tả
Hôm nay là sinh nhật của bạn! Bạn đã chuẩn bị một chiếc bánh hình chữ nhật và mời người bạn đến chung vui. Chiếc bánh có thể xem là một hình chữ nhật có các cạnh song song với các trục tọa độ trên mặt phẳng , với một góc nằm tại điểm và góc đối diện nằm tại điểm .
Lần lượt từng người bạn đến tặng quà và xin một phần bánh. Người bạn thứ chỉ vào một điểm và yêu cầu bạn cắt hai nhát thẳng xuất phát từ điểm đó:
- một nhát cắt sang trái hoặc sang phải, song song với trục ;
- một nhát cắt lên trên hoặc xuống dưới, song song với trục .
Sau khi cắt, người bạn đó nhận toàn bộ phần bánh nằm trong góc phần tư tạo bởi hai nhát cắt. Lưu ý rằng điểm được chỉ có thể không nằm bên trong chiếc bánh. Cũng có thể trong góc phần tư đó không còn chút bánh nào, vì người bạn đó có thể đang no.
Sau mỗi cặp nhát cắt, chiếc bánh của bạn ngày càng nhỏ đi. Bạn muốn biết mỗi người bạn có nhận được phần bánh công bằng hay không. Với mỗi người bạn, hãy tìm diện tích phần bánh mà người đó nhận được.
Dữ liệu vào
Dữ liệu vào gồm nhiều bộ dữ liệu. Dòng đầu tiên chứa số bộ dữ liệu (). Tiếp theo là mô tả các bộ dữ liệu:
- Dòng đầu tiên chứa ba số nguyên , và (; ): kích thước chiếc bánh và số người bạn được mời.
- Dòng thứ trong dòng tiếp theo chứa hai số nguyên , và hai ký tự , (; ;
L,R;U,D): tọa độ điểm mà người bạn thứ chỉ vào và hướng cắt:- là hướng của nhát cắt thứ nhất:
Llà cắt sang trái,Rlà cắt sang phải; - là hướng của nhát cắt thứ hai:
Ulà cắt lên trên,Dlà cắt xuống dưới.
- là hướng của nhát cắt thứ nhất:
Dữ liệu đảm bảo tổng của tất cả các bộ dữ liệu không vượt quá .
Dữ liệu ra
Với mỗi người bạn, in ra diện tích phần bánh mà người đó nhận được, mỗi số trên một dòng.
Ràng buộc
- .
- ; .
- ; .
- Tổng của tất cả các bộ dữ liệu không vượt quá .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 3 8 6 2 4 3 R U 7 4 R D 8 6 2 4 3 R U 1 1 L D 8 6 2 4 3 R U 5 4 R U |
12 3 12 1 12 0 |
Ở bộ dữ liệu thứ nhất, bánh rộng và cao . Người bạn thứ nhất nhận phần bánh có diện tích . Người bạn thứ hai chỉ vào điểm và cắt sang phải, xuống dưới: góc phần tư là , ; phần bánh còn lại trong đó là có diện tích . Ở bộ dữ liệu thứ hai, người bạn thứ hai nhận phần có diện tích . Ở bộ dữ liệu thứ ba, góc phần tư của người bạn thứ hai nằm trọn trong phần đã bị cắt đi, nên người đó không nhận được gì. |
| 1 5 4 4 2 1 L U 3 2 R D 1 3 R U 4 0 L U |
6 4 3 6 |
Ví dụ bổ sung (không có trong đề gốc). Người bạn thứ nhất nhận , người thứ hai nhận . Người thứ ba nhận phần còn lại trong , , tức , diện tích . Người thứ tư nhận , và , tổng diện tích . |
Bình luận