trang chủ / đề bài / icpcwf05_b

Mạng GSM đơn giản hoá

Đề bài

Mô tả

Điện thoại di động đã thay đổi đáng kể cách chúng ta sống trong thập kỷ qua. Điện thoại di động kết nối với nhau qua nhiều giao thức khác nhau. Một trong những mạng phổ biến nhất cho điện thoại di động là mạng GSM (Global System for Mobile Communication).

Trong một mạng GSM thông thường, điện thoại di động kết nối với BTS (Base Transceiver Station, trạm thu phát gốc) gần nhất. Một BSC (Base Station Center) điều khiển nhiều BTS. Nhiều BSC được điều khiển bởi một MSC (Mobile Services Switching Center), và MSC này duy trì kết nối với nhiều MSC khác, một mạng PSTN (Public Switched Telecom Network) và một mạng ISDN (Integrated Services Digital Network).

Bài toán này dùng một mô hình đơn giản hoá của mạng GSM thông thường. Mạng đơn giản hoá của chúng ta gồm không quá năm mươi trạm BTS. Khi đang dùng, một điện thoại di động luôn kết nối với trạm BTS gần nó nhất. Vùng do một trạm BTS phục vụ gọi là một ô (cell). Khi một điện thoại đang hoạt động di chuyển, mỗi lần vượt qua ranh giới giữa hai ô, nó phải chuyển liền mạch từ trạm BTS này sang trạm BTS khác. Cho bản đồ gồm các thành phố, các con đường và các trạm BTS, hãy tìm số lần chuyển trạm BTS ít nhất cần thiết để đi từ một thành phố đến một thành phố khác.

Hình: Các thành phố là các hình vuông, các trạm BTS là các hình thang. Các đoạn liền nét là đường đi. Các đường nét đứt chia mặt phẳng thành 9 ô. Số lần chuyển ít nhất để đi từ thành phố 1 đến thành phố 6 là (2+1+0)=3. Thành phố 7 bị cô lập, không thể đi tới.

Mỗi trạm và mỗi thành phố được xem là một điểm trong hệ toạ độ Descartes hai chiều. Nếu có đường đi giữa hai thành phố thì đường đó là đoạn thẳng nối hai thành phố. Chẳng hạn trong hình, đi trên đường từ thành phố 1 đến thành phố 2 phải vượt qua hai ranh giới ô nên cần hai lần chuyển. Đi từ thành phố 2 đến thành phố 5 vượt qua một ranh giới, còn đi từ thành phố 5 đến thành phố 6 không cần chuyển lần nào. Đi theo lộ trình này từ thành phố 1 đến thành phố 6 cần tổng cộng ba lần chuyển. Mọi lộ trình khác từ thành phố 1 đến thành phố 6 đều cần không ít hơn ba lần chuyển. Nếu có nhiều cách đi từ một thành phố đến một thành phố khác, chương trình của bạn phải tìm lộ trình tối ưu.

Dữ liệu vào

Dữ liệu gồm nhiều bộ test. Dòng đầu tiên của mỗi bộ test chứa bốn số nguyên: B là số trạm BTS, C là số thành phố, R là số con đường và Q là số truy vấn.

  • B dòng tiếp theo, mỗi dòng chứa hai số thực x và y là toạ độ của một trạm BTS.
  • C dòng tiếp theo, dòng thứ i chứa hai số thực xi, yi là toạ độ của thành phố thứ i (1≤i≤C).
  • R dòng tiếp theo, mỗi dòng chứa hai số nguyên m và n (1≤m,n≤C) cho biết có một con đường nối thành phố thứ m và thành phố thứ n.
  • Q dòng tiếp theo, mỗi dòng chứa hai số nguyên s và d (1≤s,d≤C) là thành phố xuất phát và thành phố đích.

Dữ liệu kết thúc bằng một dòng chứa bốn số 0.

Dữ liệu ra

Với mỗi bộ test, in ra Q+1 dòng như trong ví dụ. Dòng đầu tiên là số thứ tự của bộ test (Case 1:, Case 2:, ...). Tiếp theo là Q dòng, mỗi dòng ứng với một truy vấn, chứa một số nguyên là số lần chuyển trạm ít nhất để đi từ thành phố s đến thành phố d. Nếu không thể đi từ thành phố s đến thành phố d, in ra dòng Impossible.

Ràng buộc

  • 1≤B≤50, 1≤C≤50, 0≤R≤250, 1≤Q≤10.
  • Mọi toạ độ có giá trị tuyệt đối không quá 1000 và có không quá 2 chữ số sau dấu thập phân.
  • Không có hai trạm nào trùng vị trí. Không có hai thành phố nào trùng vị trí, và không có thành phố nào nằm trên ranh giới giữa các ô.
  • Không có con đường nào trùng với ranh giới giữa các ô, và không có con đường nào đi qua một điểm nằm trên ranh giới của ba ô trở lên.
  • Các điều kiện trên vẫn đúng khi toạ độ thay đổi một lượng rất nhỏ: trên mỗi con đường, hai điểm chuyển trạm liên tiếp (và hai đầu đường) cách nhau ít nhất 0,002.
  • Mỗi file có không quá 100 bộ test.

Ví dụ

Input Output Giải thích
9 7 6 2
5 5
15 5
25 5
5 15
15 15
25 15
5 25
15 25
25 25
8 2
22 3
8 12
18 18
22 12
28 16
28 8
1 2
1 3
2 5
3 4
4 5
5 6
1 6
1 7
0 0 0 0
Case 1:
3
Impossible
Đây là bản đồ trong hình. Đường 1-2 cần 2 lần chuyển, 2-5 cần 1, 5-6 cần 0; lộ trình 1,3,4,5,6 cũng cần 1+1+1+0=3. Thành phố 7 không có đường nào.
2 3 3 2
0 0
10 0
-1 1
11 1
4 8
1 2
2 3
1 3
1 2
2 2
1 2 0 2
0 0
3.5 -2
7 7
1 2
1 1
0 0 0 0
Case 1:
1
0
Case 2:
Impossible
0
Ví dụ tự thêm. Bộ 1: hai ô ngăn cách bởi đường thẳng x=5; mọi lộ trình từ thành phố 1 sang thành phố 2 đều phải vượt ranh giới này một lần. Bộ 2: không có đường nào, nhưng đi từ một thành phố đến chính nó cần 0 lần chuyển.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0