Raise the Roof

Các nhà nhân chủng học đã khám phá một điều bất ngờ về một xã hội Hy Lạp cổ đại gồm toàn những nhà hình học: họ yêu tiệc tùng chẳng kém gì toán học! Trên thực tế, qua nhiều năm họ liên tục tổ chức những bữa tiệc ngày càng lớn, nên phải nâng mái phòng khiêu vũ để giữ mức tiếng ồn ở ngưỡng chấp nhận được.

Ta biết rằng mái phòng khiêu vũ luôn được đỡ bởi đầu mút của đúng ba cột. Mỗi cột là một đoạn thẳng mảnh vô hạn, bắt đầu trên sàn và dựng vuông góc với sàn. Mỗi khi muốn nâng mái, họ bắt đầu bằng việc dỡ mái hiện tại. Sau đó, họ xây một cột mới tại một vị trí chưa có cột. Cuối cùng, họ đặt một mái mới lên đầu cột mới và hai cột được xây gần đây nhất trong số các cột đã tồn tại. Vì những lý do huyền bí, không bao giờ có ba chân cột thẳng hàng và cũng không bao giờ có bốn đầu cột đồng phẳng.

Mỗi mái là một đa giác lồi nằm trong mặt phẳng được xác định bởi ba đầu cột đỡ nó. Với mỗi cột \(c\) được xây trước ba cột đỡ mái, mái không giao \(c\) tại bất kỳ điểm nào và đủ rộng để che phủ không gian phía trên \(c\). Mái không chạm sàn. Các mái khác nhau không nhất thiết có cùng hình dạng.

Trong một cuộc khai quật khảo cổ, bạn tìm thấy toàn bộ \(N\) cột mà xã hội này từng xây, nhưng không còn mái nào. Bạn muốn xác định một thứ tự khả dĩ mà các cột đã được xây, phù hợp với các quy tắc trên.

Một thứ tự khả dĩ là một hoán vị của \(N\) cột sao cho, với mọi tiền tố có độ dài ít nhất 4, tồn tại một mái (một đa giác lồi) chứa đầu mút của ba cột cuối cùng trong tiền tố; đồng thời, với mọi cột khác trong tiền tố có đầu mút tại \((x,y,h)\), mái chứa một điểm \((x,y,z)\) với \(z>h\).

Dữ liệu vào

Dòng đầu tiên chứa số lượng bộ test \(T\). Sau đó là \(T\) bộ test.

Mỗi bộ test bắt đầu bằng một dòng chứa số nguyên \(N\), số lượng cột. Tiếp theo là \(N\) dòng; dòng thứ \(i\) chứa ba số nguyên \(X_i\), \(Y_i\) và \(H_i\), lần lượt là tọa độ X, tọa độ Y và độ cao so với mặt đất của đầu cột thứ \(i\).

Dữ liệu ra

Với mỗi bộ test, in một dòng có dạng Case #x: y1 y2 ... yN, trong đó x là số thứ tự bộ test (bắt đầu từ 1), và mỗi yi là một số nguyên khác nhau từ 1 đến \(N\). Chúng biểu diễn một thứ tự xây cột khả dĩ, trong đó yi là chỉ số trong input của cột được xây thứ \(i\).

Đề bài bảo đảm luôn có ít nhất một đáp án hợp lệ. Nếu có nhiều đáp án, bạn có thể in bất kỳ đáp án nào.

Ràng buộc

• \(1 \le T \le 100\).
• \(-10^6 \le X_i \le 10^6\) với mọi \(i\).
• \(-10^6 \le Y_i \le 10^6\) với mọi \(i\).
• \(1 \le H_i \le 10^6\) với mọi \(i\).
• \((X_i,Y_i)\), \((X_j,Y_j)\) và \((X_k,Y_k)\) không thẳng hàng với mọi bộ chỉ số \(i,j,k\) đôi một phân biệt.
• \((X_i,Y_i,H_i)\), \((X_j,Y_j,H_j)\), \((X_k,Y_k,H_k)\) và \((X_l,Y_l,H_l)\) không đồng phẳng với mọi bộ chỉ số \(i,j,k,l\) đôi một phân biệt.

Phân nhóm

• Test Set 1 (Visible): \(4 \le N \le 10\).
• Test Set 2 (Hidden): \(4 \le N \le 1000\).

Đ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
5
-1 0 3
1 2 4
1 -2 4
3 1 3
3 -1 2
4
1 1 1
2 2 3
2 3 4
10 11 120
4
1 1 1
2 2 3
2 3 4
10 11 12

Case #1: 5 4 3 1 2
Case #2: 3 2 1 4
Case #3: 1 2 4 3

Nguồn

Google Code Jam 2018, Vòng 3, bài Raise the Roof.

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