Trong một căn phòng hình vuông lớn, có hai nguồn sáng điểm: một nguồn màu đỏ và một nguồn màu xanh lá cây. Ngoài ra còn có \(n\) cột hình trụ.

Ánh sáng truyền theo đường thẳng và bị hấp thụ bởi các bức tường và cột. Do đó, các cột sẽ đổ bóng: chúng không cho ánh sáng đi qua. Có những vị trí trong phòng không có ánh sáng nào chiếu tới (màu đen), những nơi chỉ có một trong hai nguồn sáng chiếu tới (đỏ hoặc xanh lá), và những nơi cả hai nguồn sáng đều chiếu tới (vàng). Hãy tính tổng diện tích của mỗi loại trong bốn màu này trong phòng. Không tính diện tích của các cột.

Dữ liệu vào

• Dòng đầu tiên chứa số lượng bộ thử nghiệm, \(T\).

Mỗi bộ thử nghiệm bao gồm, theo thứ tự:

• Một dòng chứa tọa độ \(x\), \(y\) của nguồn sáng đỏ.
• Một dòng chứa tọa độ \(x\), \(y\) của nguồn sáng xanh lá.
• Một dòng chứa số lượng cột \(n\).
• \(n\) dòng mô tả các cột. Mỗi dòng chứa 3 số \(x\), \(y\), \(r\). Cột là một hình tròn có tâm (\(x\), \(y\)) và bán kính \(r\).

Căn phòng là hình vuông được mô tả bởi \(0 \le x, y \le 100\). Các cột, tường phòng và nguồn sáng đều rời nhau, chúng không chồng lấn hoặc chạm nhau.

Dữ liệu ra

Đối với mỗi bộ thử nghiệm, hãy in ra:

Case #X:
Black: B
Red: R
Green: G
Yellow: Y

trong đó \(X\) là số thứ tự bộ thử nghiệm, bắt đầu từ 1, và mỗi diện tích là một số thực.

Bất kỳ câu trả lời nào có sai số tuyệt đối hoặc tương đối không quá \(10^{-5}\) đều sẽ được chấp nhận.

Case #X:
black area
red area
green area
yellow area

Ràng buộc

Tất cả các số nhập vào đều là số nguyên.
\(1 \le T \le 15\)
\(0 \le x, y \le 100\)
\(1 \le r \le 49\)

Phân nhóm

• Small dataset: \(0 \le n \le 1\).
• Large dataset: \(0 \le n \le 50\).

Đ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ụ

1
5 50
95 50
1
50 50 10

Case #1:
0.7656121
1437.986
1437.986
6809.104

Nguồn

Google Code Jam 2009, Chung kết thế giới, bài Lights.

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