trang chủ / đề bài / icpc25_reg_c

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 q 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 Oxy, với một góc nằm tại điểm (0,0) và góc đối diện nằm tại điểm (w,h).

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ứ i chỉ vào một điểm (xi,yi) 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 Ox;
  • một nhát cắt lên trên hoặc xuống dưới, song song với trục Oy.

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 τ (1≤τ≤104). Tiếp theo là mô tả các bộ dữ liệu:

  • Dòng đầu tiên chứa ba số nguyên w, h và q (1≤w,h≤109; 1≤q≤105): kích thước chiếc bánh và số người bạn được mời.
  • Dòng thứ i trong q dòng tiếp theo chứa hai số nguyên xi, yi và hai ký tự hor, ver (0≤xi≤w; 0≤yi≤h; hor∈{L, R}; ver∈{U, D}): tọa độ điểm mà người bạn thứ i chỉ vào và hướng cắt:
    • hor là hướng của nhát cắt thứ nhất: hor= L là cắt sang trái, hor= R là cắt sang phải;
    • ver là hướng của nhát cắt thứ hai: ver= U là cắt lên trên, ver= D là cắt xuống dưới.

Dữ liệu đảm bảo tổng q của tất cả các bộ dữ liệu không vượt quá 105.

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

  • 1≤τ≤104.
  • 1≤w,h≤109; 1≤q≤105.
  • 0≤xi≤w; 0≤yi≤h.
  • Tổng q của tất cả các bộ dữ liệu không vượt quá 105.

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 8 và cao 6. Người bạn thứ nhất nhận phần bánh [4,8]×[3,6] có diện tích 4·3=12. Người bạn thứ hai chỉ vào điểm (7,4) và cắt sang phải, xuống dưới: góc phần tư là x≥7, y≤4; phần bánh còn lại trong đó là [7,8]×[0,3] có diện tích 3. Ở bộ dữ liệu thứ hai, người bạn thứ hai nhận phần [0,1]×[0,1] có diện tích 1. Ở 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 [0,2]×[1,4], người thứ hai nhận [3,5]×[0,2]. Người thứ ba nhận phần còn lại trong x≥1, y≥3, tức [2,5]×[3,4], diện tích 3. Người thứ tư nhận [0,3]×[0,1], [2,3]×[1,2] và [2,4]×[2,3], tổng diện tích 3+1+2=6.

Bình luận

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

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0