Bạn được cho một tập \(P\) gồm \(N\) điểm phân biệt trên mặt phẳng hai chiều. Hãy tìm một tập tam giác có số lượng lớn nhất sao cho:

• Mỗi đỉnh của một tam giác trong tập phải là một điểm thuộc \(P\), và mỗi điểm trong \(P\) là đỉnh của nhiều nhất một tam giác trong tập.
• Mỗi tam giác trong tập có diện tích dương, tức ba đỉnh của nó không thẳng hàng.
• Với hai cạnh bất kỳ của các tam giác trong tập, giao của chúng hoặc rỗng, hoặc là một đầu mút của một trong hai cạnh.
• Với hai tam giác bất kỳ trong tập, giao của hai miền nằm hoàn toàn bên trong các tam giác hoặc rỗng, hoặc bằng toàn bộ một trong hai miền đó.

Ví dụ, tập tam giác dưới đây thỏa định nghĩa trên.

Ngược lại, mỗi cặp gồm một tam giác vàng và một tam giác đỏ trong hình dưới đây đều không thỏa định nghĩa.

Dữ liệu vào

Dòng đầu tiên chứa số 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\). Tiếp theo là \(N\) dòng; dòng thứ \(i\) chứa hai số nguyên \(X_i\) và \(Y_i\), là tọa độ của điểm thứ \(i\).

Dữ liệu ra

Với mỗi bộ test, in một dòng Case #x: y, trong đó \(x\) là số thứ tự bộ test (bắt đầu từ \(1\)) và \(y\) là số tam giác lớn nhất của một tập thỏa các tính chất yêu cầu. Sau đó in thêm \(y\) dòng. Dòng thứ \(j\) chứa \(p_j\ q_j\ r_j\), cho biết tam giác thứ \(j\) trong tập đề xuất dùng các điểm thứ \(p_j\), \(q_j\) và \(r_j\) của dữ liệu vào làm đỉnh. Các điểm đầu vào được đánh số từ \(1\).

Ràng buộc

• \(1\le T\le100\).
• \(-10^9\le X_i\le10^9\) với mọi \(i\).
• \(-10^9\le Y_i\le10^9\) với mọi \(i\).
• \((X_i,Y_i)\ne(X_j,Y_j)\) với mọi \(i\ne j\).

Phân nhóm

• Test Set 1 (phán quyết hiển thị): \(3\le N\le12\).
• Test Set 2 (phán quyết ẩn): \(3\le N\le3000\).

Đ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
9
8 2
10 2
2 0
0 5
2 3
10 4
10 0
8 3
2 4
7
0 0
0 3
3 0
0 1
1 0
1 1
2 2
3
0 0
0 1
0 2

Case #1: 3
3 4 5
1 7 9
6 2 8
Case #2: 2
2 3 1
6 5 4
Case #3: 0

Nguồn

Google Code Jam 2022, Chung kết thế giới, bài Triangles.

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