“Tôi nói rằng chúng ta phải tiến lên, không phải lùi lại; \n> đi lên, không phải tiến về phía trước; \n> và luôn xoay, xoay, xoay về phía tự do!” \n> — Kodos, cựu ứng cử viên Tổng thống Hoa Kỳ.

Sau khi nghe câu nói đầy cảm hứng này từ ứng cử viên tổng thống đầu tiên của Mỹ đến từ hành tinh Rigel VII, bạn đã quyết định rằng mình cũng muốn xoay (rotate) để hướng tới tự do. Trong bài toán này, bạn có thể coi "tự do" là việc ở cách xa vị trí xuất phát nhất có thể.

Thiên hà là một mặt phẳng hai chiều. Tàu vũ trụ của bạn bắt đầu tại gốc tọa độ, vị trí \((0, 0)\). Có \(N\) ngôi sao trong thiên hà. Mỗi phút, bạn có thể chọn một ngôi sao và xoay tàu vũ trụ của mình 90 độ theo chiều kim đồng hồ quanh ngôi sao đó. Bạn cũng có thể chọn đứng yên tại chỗ.

Hỏi bạn có thể đi bao xa so với gốc tọa độ sau \(M\) phút?

Hình ảnh minh họa 3 lần xoay đầu tiên cho một lộ trình có thể có trong ví dụ 1. Lưu ý rằng lộ trình này không nhất thiết phải là một phần của bất kỳ giải pháp tối ưu nào.

Dữ liệu vào

Dòng đầu tiên của đầu vào cho biết số lượng bộ test, \(T\). \(T\) bộ test tiếp theo, bắt đầu bằng hai dòng chứa các số nguyên \(N\) và \(M\). \(N\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(X_i\) và \(Y_i\), đại diện cho vị trí của các ngôi sao.

Dữ liệu ra

Đối với mỗi bộ test, hãy xuất một dòng chứa "Case #x: \(D\)", trong đó x là số thứ tự bộ test (bắt đầu từ 1) và \(D\) là khoảng cách từ gốc tọa độ đến vị trí cuối cùng tối ưu. Các câu trả lời có sai số tuyệt đối hoặc tương đối không lớn hơn \(10^{-6}\) sẽ được chấp nhận.

Ràng buộc

• \(1 \le T \le 100\);
• \(-1000 \le X_i \le 1000\);
• \(-1000 \le Y_i \le 1000\).
• Không có hai ngôi sao nào ở cùng một vị trí.
• Có thể có một ngôi sao tại gốc tọa độ.

Phân nhóm

• Test set 1 (Visible): \(1 \le N \le 10\); \(1 \le M \le 10\).
• Test set 2 (Hidden): \(1 \le N \le 5000\); \(1 \le M \le 10^8\).

Đ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 4
1 -2
4 1
0 2
1
4
-5 0
2
5
-1 1
-2 2

Case #1: 6.3245553203
Case #2: 10.0000000000
Case #3: 6.3245553203

Nguồn

Google Code Jam 2012, Chung kết thế giới, bài Twirling Towards Freedom.

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