Ngày xửa ngày xưa, một nền văn minh ngoài hành tinh đã xây dựng một tượng đài khổng lồ. Sàn của tượng đài trông như thế này:

###############
#.............#
#.###########.#
#.#.........#.#
#.#.#######.#.#
#.#.#.....#.#.#
#.#.#.###.#.#.#
#.#.#.#.#.#.#.#
#.#.#.###.#.#.#
#.#.#.....#.#.#
#.#.#######.#.#
#.#.........#.#
#.###########.#
#.............#
###############

Mỗi ký tự # đại diện cho một viên gạch màu đỏ, và mỗi ký tự . đại diện cho một viên gạch màu xanh. Hoa văn này kéo dài hàng dặm (đối với mục đích của bài toán này, bạn có thể giả định nó là vô tận). Ngày nay, chỉ còn lại một vài viên gạch. Những viên còn lại đã bị hư hại bởi mưa methane và bão bụi. Cho biết vị trí và màu sắc của các viên gạch còn lại, bạn có thể tìm thấy tâm của hoa văn không?

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào cho biết số lượng bộ test, \(T\). \(T\) bộ test tiếp theo. Mỗi bộ bắt đầu bằng một dòng chứa \(N\), số lượng viên gạch còn lại. \(N\) dòng tiếp theo, mỗi dòng chứa \(X_i\), \(Y_i\), và màu của viên gạch (hoặc # hoặc .).

Dữ liệu ra

Với mỗi bộ test, xuất một dòng chứa "Case #c: \(X\) \(Y\)", trong đó c là số thứ tự bộ test (bắt đầu từ 1) và (\(X\), \(Y\)) là vị trí tâm của hoa văn. Nếu có nhiều hơn một câu trả lời khả thi, hãy xuất (\(X\), \(Y\)) gần (\(0, 0\)) nhất theo khoảng cách Manhattan (khoảng cách theo x cộng với khoảng cách theo y). Nếu vẫn còn hòa, hãy xuất điểm có \(X\) lớn nhất. Nếu vẫn còn hòa sau đó, hãy xuất điểm có \(Y\) lớn nhất. Nếu không có câu trả lời khả thi, hãy xuất "Case #c: Too damaged".

Ràng buộc

• \(1 \le T \le 50\).
• Danh sách các tọa độ trong mỗi bộ test sẽ không chứa các phần tử trùng lặp.

Phân nhóm

• Test set 1 (Visible Verdict):
• \(1 \le N \le 100\).
• \(-100 \le X_i \le 100\).
• \(-100 \le Y_i \le 100\).
• Test set 2 (Hidden Verdict):
• \(1 \le N \le 1000\).
• \(-10^{15} \le X_i \le 10^{15}\).
• \(-10^{15} \le Y_i \le 10^{15}\).

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

6
1
0 0 .
1
0 0 #
3
0 0 #
0 1 #
1 0 #
5
50 30 #
49 30 #
49 31 #
49 32 #
50 32 #
2
-98 0 #
99 50 .
4
88 88 .
88 89 .
89 88 .
89 89 .

Case #1: 0 0
Case #2: 1 0
Case #3: 1 1
Case #4: 50 31
Case #5: 1 0
Case #6: Too damaged

Nguồn

Google Code Jam 2012, Chung kết thế giới, bài Xeno-archaeology.

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