Min Perimeter

Bạn sẽ được cho một tập hợp các điểm với tọa độ nguyên. Nhiệm vụ của bạn là tính chu vi nhỏ nhất của một tam giác có các đỉnh phân biệt từ tập hợp các điểm này.

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 theo sau. Mỗi bộ test chứa một số nguyên \(n\) ở dòng đầu tiên, là số lượng điểm trong tập hợp. \(n\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(x_i, y_i\). Đây là tọa độ của điểm thứ \(i\). Không có nhiều hơn một điểm tại cùng một tọa độ.

Dữ liệu ra

Với mỗi bộ test, xuất ra:

Case #X: Y

trong đó \(X\) là số thứ tự của bộ test và \(Y\) là chu vi nhỏ nhất. Các câu trả lời có sai số tương đối hoặc tuyệt đối không quá \(10^{-5}\) sẽ được coi là chính xác. Các tam giác suy biến — tam giác có diện tích bằng 0 — được chấp nhận.

Ràng buộc

• \(1 \le T \le 15\)
• \(0 \le x_i, y_i \le 10^9\)

Phân nhóm

• Small dataset: \(3 \le n \le 10000\).
• Large dataset: \(3 \le n \le 1000000\).

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

1
10
0 0
1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9

Case #1: 5.656854

Nguồn

Google Code Jam 2009, Chung kết thế giới, bài Min Perimeter.

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