Bạn vừa mới mua một trang trại lớn và muốn xây dựng một hàng rào xung quanh nó. Đã có sẵn \(N\) cọc rào trong trang trại của bạn.

Bạn sẽ thêm các đoạn hàng rào là các đường thẳng nối các cọc rào. Thật không may, vì những lý do pháp lý, luật sư của bạn nhấn mạnh rằng bạn thực sự phải sử dụng tất cả các cọc rào, nếu không mọi chuyện sẽ trở nên tồi tệ.

Trong bài toán này, các cọc rào được biểu diễn dưới dạng các điểm trên mặt phẳng 2 chiều. Bạn muốn xây dựng hàng rào bằng cách sắp xếp các cọc rào theo một thứ tự nào đó, sau đó nối cọc thứ nhất với cọc thứ hai, thứ hai với thứ ba, và cuối cùng là cọc cuối cùng với cọc đầu tiên. Các đoạn hàng rào bạn tạo ra phải tạo thành một đa giác không tự cắt. Nghĩa là, tại mỗi cọc rào chỉ có đúng hai đoạn hàng rào nối vào, và tại mọi điểm khác có tối đa một đoạn hàng rào đi qua.

Bây giờ, điều đó khá dễ dàng, nhưng bạn cũng muốn bảo toàn thực tế là trang trại của bạn rất lớn! Sẽ không vui chút nào nếu bạn rào lại phần lớn trang trại của mình bằng các hàng rào. Vì vậy, bạn muốn tạo ra hàng rào sao cho diện tích bao quanh lớn hơn một nửa diện tích tối đa mà bạn có thể bao quanh nếu bạn được phép không sử dụng tất cả các cọc.

Dữ liệu vào

Dòng đầu tiên của đầu vào cho biết số lượng bộ thử nghiệm, \(T\). \(T\) bộ thử nghiệm tiếp theo. Dòng đầu tiên của mỗi bộ thử nghiệm chứa số \(N\) các cọc rào. Các cọc được đánh số từ \(0\) đến \(N - 1\). Mỗi dòng trong \(N\) dòng tiếp theo chứa hai số nguyên \(X_i\) và \(Y_i\) cách nhau bởi một khoảng trắng: tọa độ của cọc thứ \(i\).

Dữ liệu ra

Đối với mỗi bộ thử nghiệm, hãy xuất một dòng chứa "Case #x: ", trong đó x là số thứ tự bộ thử nghiệm (bắt đầu từ 1), tiếp theo là \(N\) số nguyên phân biệt từ \(0\) đến \(N - 1\), cách nhau bởi dấu cách. Đó là số hiệu của các cọc rào, theo chiều kim đồng hồ hoặc ngược chiều kim đồng hồ, mà bạn sẽ sử dụng để xây dựng hàng rào. Lưu ý rằng cọc đầu tiên và cọc cuối cùng được nối với nhau.

Nếu có nhiều giải pháp, hãy in bất kỳ giải pháp nào trong số đó.

Ràng buộc

• Các cọc rào sẽ ở \(N\) điểm duy nhất và không cùng nằm trên một đường thẳng.

Phân nhóm

• Small dataset (Test set 1):

  • \(1 \le T \le 100\)
  • \(3 \le N \le 10\)
  • \(-100 \le X_i, Y_i \le 100\)

  • Large dataset (Test set 2):

  • \(1 \le T \le 30\)

  • \(3 \le N \le 1000\)
  • \(-50000 \le X_i, Y_i \le 50000\)

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

3
4
1 2
2 0
0 0
1 1
5
0 0
1 1
2 2
0 2
2 0
3
0 0
1 0
0 1

Case #1: 0 1 2 3
Case #2: 0 1 4 2 3
Case #3: 0 2 1

Nguồn

Google Code Jam 2013, Vòng 3, bài Rural Planning.

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