Cắt bánh

Đề bài

Hôm nay là sinh nhật của bạn và người anh/chị/em sinh đôi của bạn. Để ăn mừng, hai bạn có một chiếc bánh hình chữ nhật để cùng chia sẻ. Chiếc bánh được trang trí bằng \(\mathbf{N}\) mảng kem phủ hình tam giác (các mảng này có thể chồng lên nhau). Tất cả các mảng kem đều được tạo bằng cùng một khuôn tam giác, vì vậy chúng có cùng hình dạng và hướng. Mặc dù bạn và người sinh đôi rất giống nhau, sở thích về kem phủ của hai người lại rất khác biệt. Cụ thể, mỗi người có một giá trị thưởng thức khác nhau đối với từng mảng kem. Giá trị thưởng thức của bạn khi ăn toàn bộ mảng kem thứ \(i\) là \(\mathbf{A_i}\), còn của người sinh đôi là \(\mathbf{B_i}\). Nếu một người chỉ ăn một phần mảng kem, họ nhận được giá trị thưởng thức tỉ lệ với diện tích đã ăn. Ví dụ, nếu bạn ăn \(\frac{2}{3}\) diện tích của mảng kem thứ \(i\), bạn sẽ nhận được \(\frac{2\mathbf{A_i}}{3}\) giá trị thưởng thức từ mảng đó. Lưu ý rằng có thể tồn tại những vị kem mà bạn hoặc người sinh đôi không thích, nên \(\mathbf{A_i}\) và/hoặc \(\mathbf{B_i}\) có thể âm.

Bạn sẽ cắt chiếc bánh thành hai miếng hình chữ nhật bằng một đường cắt thẳng đứng duy nhất (song song với trục Y). Sau khi cắt, bạn sẽ ăn miếng bên trái và người sinh đôi sẽ ăn miếng bên phải. Tổng giá trị thưởng thức của bạn là tổng giá trị thưởng thức nhận được từ toàn bộ phần kem nằm bên trái đường cắt. Tương tự, giá trị thưởng thức của người sinh đôi là tổng giá trị thưởng thức nhận được từ toàn bộ phần kem nằm bên phải đường cắt.

Để công bằng nhất có thể, bạn muốn cắt bánh sao cho trị tuyệt đối của hiệu giữa tổng giá trị thưởng thức của bạn và của người sinh đôi là nhỏ nhất. Với \(\mathbf{N}\) mảng kem phủ hình tam giác trên một chiếc bánh hình chữ nhật, trị tuyệt đối nhỏ nhất có thể của hiệu giữa tổng giá trị thưởng thức của hai người là bao nhiêu?

Dữ liệu vào

Dòng đầu tiên chứa số lượng bộ test \(\mathbf{T}\). Sau đó là \(\mathbf{T}\) bộ test. Mỗi bộ test bắt đầu bằng một dòng chứa ba số nguyên dương \(\mathbf{N}\), \(\mathbf{W}\) và \(\mathbf{H}\), lần lượt biểu thị số mảng kem phủ trên bánh, chiều rộng và chiều cao của mặt bánh. Góc dưới bên trái của bánh nằm tại \((0, 0)\) và góc trên bên phải nằm tại \((\mathbf{W}, \mathbf{H})\).

Tiếp theo là một dòng mô tả khuôn của mảng kem, chứa bốn số nguyên \(\mathbf{P}\), \(\mathbf{Q}\), \(\mathbf{R}\) và \(\mathbf{S}\). Khuôn là một tam giác có các đỉnh tại \((0, 0)\), \((\mathbf{P}, \mathbf{Q})\) và \((\mathbf{R}, \mathbf{S})\).

Sau đó là \(\mathbf{N}\) dòng. Dòng thứ \(i\) chứa bốn số nguyên \(\mathbf{X_i}\), \(\mathbf{Y_i}\), \(\mathbf{A_i}\) và \(\mathbf{B_i}\). Mảng thứ \(i\) là tam giác có các đỉnh tại \((\mathbf{X_i}, \mathbf{Y_i})\), \((\mathbf{X_i} + \mathbf{P}, \mathbf{Y_i} + \mathbf{Q})\) và \((\mathbf{X_i} + \mathbf{R}, \mathbf{Y_i} + \mathbf{S})\). Bạn nhận được \(\mathbf{A_i}\) giá trị thưởng thức khi ăn mảng đó, còn người sinh đôi nhận được \(\mathbf{B_i}\).

Dữ liệu ra

Với mỗi bộ test, in một dòng theo dạng Case #$x$: $y$/$z$, trong đó \(x\) là số thứ tự bộ test (bắt đầu từ 1), còn \(\frac{y}{z}\) là trị tuyệt đối nhỏ nhất có thể của hiệu giữa tổng giá trị thưởng thức của hai người khi dùng một đường cắt thẳng đứng, được viết dưới dạng phân số tối giản (nghĩa là \(z\) phải dương và có giá trị nhỏ nhất có thể).

Ràng buộc

Phân nhóm

Test Set 1 (Phán quyết hiển thị)

• \(1 \le \mathbf{T} \le 100\).
• \(1 \le \mathbf{N} \le 100\).
• \(3 \le \mathbf{W} \le 10^9\).
• \(3 \le \mathbf{H} \le 10^9\).
• \(-10^9 \le \mathbf{A_i} \le 10^9\) với mọi \(i\).
• \(-10^9 \le \mathbf{B_i} \le 10^9\) với mọi \(i\).
• \(0 \le \mathbf{P} \le 10^9\).
• \(-10^9 \le \mathbf{Q} \le 10^9\).
• \(0 \le \mathbf{R} \le 10^9\).
• \(-10^9 \le \mathbf{S} \le 10^9\).
• Ba đỉnh của khuôn \((0, 0)\), \((\mathbf{P}, \mathbf{Q})\) và \((\mathbf{R}, \mathbf{S})\) không thẳng hàng.
• Ba đỉnh của mỗi mảng kem hình tam giác đều nằm hoàn toàn bên trong đường biên của bánh. Cụ thể:
• \(1 \le \mathbf{X_i} \le \mathbf{W} - \max(\mathbf{P}, \mathbf{R}) - 1\) với mọi \(i\); và
• \(\max(0, -\mathbf{Q}, -\mathbf{S}) + 1 \le \mathbf{Y_i} \le \mathbf{H} - \max(0, \mathbf{Q}, \mathbf{S}) - 1\) với mọi \(i\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

4
1 5 5
3 -1 2 2
1 2 -10 5
2 100000000 50000000
80000000 0 40000000 40000000
5000001 2500000 500 -501
15000000 5000000 501 -400
2 10 10
0 2 4 2
2 2 -4 5
4 6 -6 5
3 622460462 608203753
486076103 36373156 502082214 284367873
98895371 126167607 823055173 -740793281
26430289 116311281 -398612375 -223683435
46950301 278229490 766767410 -550292032

Case #1: 5/1
Case #2: 288309900002019999899/320000000000000000
Case #3: 37/4
Case #4: 216757935773010988373334129808263414106891/187470029508637421883991794137967

Nguồn

Google Code Jam 2021, Chung kết thế giới, bài Cutting Cake.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.