Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

P148PROD - ROUND 8D - Gán tần số

Trong mạng viễn thông di động, người ta lắp đặt các trạm chuyển tiếp sóng BTS. Để tránh xuyên nhiễu, người ta sẽ gán cho hai trạm gần nhau hai tần số khác xa nhau. Trong bài toán này, giả sử các tần số là các số nguyên dương. Hai trạm gần nhau cần được gán tần số cách nhau ít nhất 2 đơn vị. Ví dụ trong hình sau là mô tả hai nhóm các trạm BTS:

Và cách sắp xếp tần số cho hai vùng đó có thể như sau:

Ta thấy, cách sắp xếp như trong hình bên phải là chưa tối ưu vì ta có thể thay trạm có giá trị 5 bằng giá trị 1. Và số tần số phải dùng chỉ là 2.

Giả sử các điểm đặt BTS là các tọa độ trong không gian 2 chiều. Hai trạm được coi là gần nhau nếu khoảng cách giữa chúng không quá 20. Hãy viết chương trình tính số lượng tần số ít nhất cần dùng để gán cho tất cả các trạm.

Input

Mỗi bộ test gồm 2 dòng:

  • Dòng đầu tiên ghi số nguyên dương N là số trạm
  • Dòng tiếp theo ghi 2*n số thực lần lượt là tọa độ của N trạm cần gán tần số

Input kết thúc khi N=0. Chú ý, có không quá 12 trạm BTS trong mỗi bộ test, và mỗi trạm có không quá 4 trạm gần với nó.

Output

Với mỗi bộ test, tính ra số lượng tần số nhỏ nhất cần dùng (f) và ghi kết quả theo khuôn dạng:

The towers in case n can be covered in f frequencies.

Example

Input:
5
0 0 5 7.5 1 -3 10.75 -20.1 12.01 -22
6
0 1 19 0 38 1 38 21 19 22 0 21
0 Output: The towers in case 1 can be covered in 3 frequencies.
The towers in case 2 can be covered in 2 frequencies.

Được gửi lên bởi:adm
Ngày:2014-03-23
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 MAWK BC C CSHARP CPP C++ 4.3.2 CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.