Trong một tương lai rất gần, ở một thiên hà lân cận, bạn muốn tạm rời trách nhiệm là nhà sản xuất sợi duy nhất của hành tinh Thundera để du lịch tới Care-a-Lot, hành tinh thư giãn nhất. Phương tiện duy nhất là mạng máy dịch chuyển liên sao.

Một máy dịch chuyển là thiết bị nhỏ trôi ở một điểm trong không gian. Bạn có thể kích hoạt nó từ xa tại bất kỳ điểm nào, nhưng theo nguyên lý bảo toàn khoảng cách dịch chuyển, nó chỉ có thể đưa bạn tới một điểm khác có đúng cùng khoảng cách \(L_1\) đến máy như trước khi dịch chuyển. Với hai điểm \((x_0,y_0,z_0)\) và \((x_1,y_1,z_1)\), khoảng cách ấy là

Ba lô phản lực đã hỏng nên bạn không thể tự di chuyển. Bạn bắt đầu ở Thundera, có thể dùng một máy để tới \(p_1\), dùng một máy khác (hoặc lại máy cũ) để tới \(p_2\), v.v.; lần dịch chuyển cuối phải đưa bạn tới chính xác Care-a-Lot.

Biết tọa độ hai hành tinh và mọi máy dịch chuyển, hãy xác định chuyến đi có thể thực hiện hay không; nếu có, tìm số lần dịch chuyển ít nhất. Hai lần dùng cùng một máy vẫn được tính là hai lần dịch chuyển riêng biệt.

Mọi tọa độ trong input là số nguyên thuộc phạm vi cho trước. Tuy nhiên, các điểm trung gian được phép có tọa độ nguyên hoặc không nguyên và không bị giới hạn phạm vi.

Dữ liệu vào

Dòng đầu chứa số test \(T\). Mỗi test bắt đầu bằng số nguyên \(N\), số máy dịch chuyển. Tiếp theo là \(N+2\) dòng, mỗi dòng chứa ba số nguyên \(X_i,Y_i,Z_i\). Dòng đầu trong số này là tọa độ Thundera, dòng thứ hai là tọa độ Care-a-Lot, và \(N\) dòng còn lại lần lượt là tọa độ các máy.

Dữ liệu ra

Với mỗi test, in Case #x: y, trong đó x là số thứ tự test bắt đầu từ 1. Nếu không thể tới Care-a-Lot thì y là IMPOSSIBLE; nếu có thể thì y là số lần dịch chuyển ít nhất.

Ràng buộc

• \(1\le T\le100\).
• \((X_i,Y_i,Z_i) e(X_j,Y_j,Z_j)\) với mọi \(i e j\); không có hai vật thể được mô tả ở cùng tọa độ.

Phân nhóm

• Test Set 1 (Visible): \(1\le N\le100\) và \(-10^3\le X_i,Y_i,Z_i\le10^3\).
• Test Set 2 (Hidden): \(1\le N\le150\) và \(-10^{12}\le X_i,Y_i,Z_i\le10^{12}\).

Đ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
1
0 0 0
0 4 0
0 3 0
2
0 0 1
0 0 11
0 0 3
0 0 0
3
0 0 0
6 2 0
6 0 0
3 0 0
6 1 0

Case #1: IMPOSSIBLE
Case #2: 3
Case #3: 2

Nguồn

Google Code Jam 2017, Chung kết thế giới, bài Teleporters.

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