Ninjutsu là võ thuật của các ninja bí ẩn. Bài tập đầu tiên của bạn là làm chủ móc dây: một chiếc móc gắn vào sợi dây rất bền, rất mảnh. Móc đã bám vào mục tiêu tại \((0,0)\); dây kéo dài sang trái và bạn ở đầu còn lại. Khi nhảy, bạn đu ngược chiều kim đồng hồ quanh mục tiêu.

Các mục tiêu khác nằm bên phải và phía trên \((0,0)\), tại \((x_i,y_i)\) với \(x_i,y_i\ge0\). Khi một điểm trong lòng dây (không phải hai đầu) chạm một hay nhiều mục tiêu, dây uốn quanh mục tiêu gần đầu đang chuyển động nhất. Bỏ qua vận tốc ban đầu: bạn đủ nhanh để tiếp tục uốn quanh các mục tiêu cho tới khi quay quanh đúng một mục tiêu.

Dây dài \(R\), nhưng trước khi đu bạn có thể cắt còn bất kỳ độ dài thực \(r\le R\). Bạn bắt đầu tại \((-r,0)\) và đu xuống (ngược chiều kim đồng hồ) hướng tới \((0,-r)\). Hỏi trong một lần đu, số khúc uốn lớn nhất là bao nhiêu? Một khúc uốn được tính khi dây chạm mục tiêu rồi quay quanh đó một góc khác 0. Ngoài các khúc uốn, dây luôn thẳng.

Ví dụ có sáu điểm \((0,0),(3,1),(12,4),(14,5),(13,7),(7,10)\) và dây dài 24. Không cắt dây, nó uốn quanh \((12,4),(14,5),(13,7)\) rồi quay quanh \((7,10)\), còn khoảng 0.1705 dây: tổng 4 khúc. Điểm \((3,1)\) không tính vì thẳng hàng với \((0,0),(12,4)\).

Cắt 0.18 đơn vị khiến dây không tới \((7,10)\) mà đi theo:

(0, 0)--(12, 4)--(14, 5)--(13, 7)--(12, 4)--(14, 5)

Nó kết thúc quanh \((14,5)\) với khoảng 1.3004 dây, tổng 5 khúc, là tối ưu.

Dữ liệu vào

Dòng đầu là \(T\). Mỗi test bắt đầu bằng \(N,R\), sau đó là \(N\) cặp số nguyên \(x_i,y_i\), bắt đầu bằng mục tiêu \((0,0)\).

Dữ liệu ra

In Case #C: k, với \(k\) là số khúc uốn tối đa.

Ràng buộc

• \(1\le T\le100\); tọa độ nguyên, các mục tiêu khác nhau, điểm đầu là \((0,0)\).
• Tồn tại một độ dài tối ưu \(r\) sao cho \(r-0.999999\) vẫn cho cùng chuỗi uốn.
• Thời gian 60 giây mỗi bộ; bộ nhớ 1 GB.

Phân nhóm

• Nhỏ: \(1\le N\le10\), \(1\le R\le1000\), \(0\le x_i,y_i\le1000\).
• Lớn: \(1\le N\le1000\), \(1\le R\le10^9\), \(0\le x_i,y_i\le10^9\).

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

6
6 24
0 0
3 1
12 4
14 5
13 7
7 10
2 1
0 0
2 0
2 1
0 0
1 0
2 10
0 0
4 0
3 50
0 0
9 0
10 0
3 12
0 0
3 0
3 4

Case #1: 5
Case #2: 0
Case #3: 0
Case #4: 2
Case #5: 12
Case #6: 3

Nguồn

Google Code Jam 2010, Chung kết thế giới, bài Ninjutsu.

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