Đức vua Tyrone Công minh và bốn người con trai của ông đã chinh phục quốc gia Carrania. Bốn người con trai ngay lập tức bắt đầu tranh cãi về việc chia đất đai giữa bốn người họ. Điểm gây tranh cãi chính là các mỏ vàng của Carrania - mỗi người con đều muốn có số lượng mỏ vàng không ít hơn bất kỳ người nào khác.

Đức vua Tyrone sớm cảm thấy mệt mỏi với những cuộc tranh cãi, đặc biệt là khi ông biết số lượng mỏ vàng là \(4N\), vì vậy việc chia chúng sẽ rất dễ dàng. Ông tập hợp các con lại, lấy một bản đồ, vẽ một chữ X lên đó và tuyên bố mỗi người con sẽ nhận được một phần tư quốc gia, với các biên giới được xác định bởi chữ X mà ông đã vẽ.

Không may thay, Đức vua Tyrone hơi bị cận thị, và bản đồ ông vẽ lên không phải là bản đồ của Carrania. Vị tể tướng của ông đã nhanh chóng giấu bản đồ đó đi, và giờ đây đang cố gắng vẽ một chữ X tương tự lên bản đồ Carrania sao cho mỗi người con nhận được số lượng mỏ vàng như nhau. Thật không may, tất cả các con trai đều đã thấy vua Tyrone vẽ chữ X, và biết rằng các biên giới phải là hai đường thẳng vuông góc - vì vậy vị tể tướng phải làm đúng như thế.

Hãy giúp ông ấy! Nhiệm vụ của bạn là vẽ hai đường thẳng vuông góc sao cho không có mỏ vàng nào nằm trên biên giới, và các biên giới chia đều các mỏ và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ộ test bắt đầu bằng một số \(N\), mô tả số lượng mỏ vàng mà mỗi người con nên nhận được. \(4N\) dòng tiếp theo, mỗi dòng chứa hai số nguyên, là tọa độ \(x_i, y_i\) của một trong các mỏ vàng. Không có ba mỏ vàng nào thẳng hàng.

Dữ liệu ra

Đối với mỗi bộ test, hãy xuất ra một dòng chứa "Case #x: \(x_a\) \(y_a\) \(x_b\) \(y_b\)", trong đó \(x\) là số thứ tự bộ test (bắt đầu từ 1), (\(x_a, y_a\)) là tọa độ của điểm giao nhau của hai biên giới, và (\(x_b, y_b\)) là tọa độ của một điểm khác trên chữ X.

Tất cả các tọa độ phải nằm trong khoảng \(-10^9\) và \(10^9\), có tối đa 9 chữ số sau dấu phẩy thập phân và không sử dụng ký hiệu lũy thừa (exponential notation). Chúng phải chính xác: chữ X kết quả sẽ được vẽ chính xác tại các tọa độ này. Bạn nên xuất ra IMPOSSIBLE nếu không có cách đặt biên giới nào phù hợp.

Ràng buộc

• \(1 \le T \le 20\)
• \(-10^6 \le x_i, y_i \le 10^6\)

Phân nhóm

• Small dataset (Test set 1 - Visible): \(1 \le N \le 10\).
• Large dataset (Test set 2 - Hidden): \(1 \le N \le 2500\).

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

2
1
0 0
1 0
0 1
1 1
1
1 0
0 1
-1 0
0 -1

Case #1: 0.5 0.5 2 0.5
Case #2: 0 0 -3 -3

Nguồn

Google Code Jam 2013, Chung kết thế giới, bài X Marks the Spot.

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