trang chủ / đề bài / icpcwf04_g

Dẫn đường

Đề bài

Mô tả

Hệ thống định vị toàn cầu (GPS) là một hệ thống dẫn đường dựa trên một tập các vệ tinh bay trên quỹ đạo cách mặt đất khoảng 20000 km. Mỗi vệ tinh đi theo một quỹ đạo đã biết và phát một tín hiệu vô tuyến mã hoá thời điểm hiện tại. Nếu một phương tiện có gắn GPS sở hữu một chiếc đồng hồ rất chính xác, nó có thể so sánh giờ của chính mình với thời điểm được mã hoá trong tín hiệu nhận được từ các vệ tinh. Vì sóng vô tuyến lan truyền với vận tốc đã biết, phương tiện tính được khoảng cách từ vị trí hiện tại của nó tới vị trí của vệ tinh tại lúc tín hiệu được phát. Bằng cách đo khoảng cách tới nhiều vệ tinh có quỹ đạo đã biết, phương tiện tính được vị trí của mình rất chính xác.

Bạn cần viết một chương trình "lái tự động" đơn giản dựa trên dẫn đường GPS. Để bài toán dễ hơn, ta xét nó trong mặt phẳng hai chiều: không cần tính tới độ cong của Trái Đất hay độ cao của vệ tinh. Ngoài ra, các vận tốc trong bài phù hợp với máy bay và sóng âm hơn là với vệ tinh và sóng vô tuyến.

Cho một tập tín hiệu đến từ các nguồn đang chuyển động, chương trình của bạn phải tính vị trí nhận tín hiệu trên mặt phẳng toạ độ Descartes. Sau đó, với một điểm đích trên mặt phẳng, chương trình phải tính hướng la bàn cần đi từ vị trí nhận tới điểm đích. Mọi hướng la bàn tính bằng độ. Hướng la bàn 0 (hướng Bắc) là chiều dương của trục y, hướng la bàn 90 (hướng Đông) là chiều dương của trục x; hướng la bàn tăng theo chiều kim đồng hồ (180 là hướng Nam, chiều âm của trục y; 270 là hướng Tây, chiều âm của trục x).

Đơn vị khoảng cách là mét. Mỗi nguồn tín hiệu chuyển động thẳng đều trên mặt phẳng với vận tốc 100 mét mỗi giây, còn tín hiệu phát ra lan truyền với vận tốc 350 mét mỗi giây. Do việc đồng bộ đồng hồ không hoàn hảo, các phép tính khoảng cách chỉ chính xác tới 0,1 mét: nếu hai điểm tính được cách nhau không quá 0,1 mét thì coi chúng là cùng một điểm. Ngoài ra, một tín hiệu có thể bị hỏng khi truyền, nên dữ liệu nhận được từ các tín hiệu có thể mâu thuẫn với nhau.

Cách xác định vị trí nhận

Nguồn thứ i ở điểm (xi,yi) tại thời điểm 0 và di chuyển theo hướng la bàn Di, nên tại thời điểm phát tín hiệu Ti nó ở điểm

Pi=(xi+100TisinDi,yi+100TicosDi).

Tín hiệu được nhận tại thời điểm t, nên vị trí nhận cách Pi đúng ri=350(t−Ti) mét, tức là nằm trên đường tròn Ci tâm Pi bán kính ri.

  • Hai đường tròn được coi là trùng nhau nếu hai tâm cách nhau không quá 0,1 và hai bán kính chênh nhau không quá 0,1.
  • Với hai đường tròn không trùng nhau, gọi d là khoảng cách hai tâm. Nếu |d−(r1+r2)|≤0,1 hoặc |d−|r1−r2||≤0,1 thì hai đường tròn tiếp xúc và có đúng một điểm chung là tiếp điểm (nằm trên đường thẳng nối hai tâm). Ngược lại, điểm chung của chúng là các giao điểm thông thường (không có hoặc có hai giao điểm).
  • Một điểm là vị trí khả dĩ nếu nó là điểm chung của hai đường tròn không trùng nhau nào đó và cách mọi đường tròn Cj không quá 0,1 mét (khoảng cách từ điểm đó tới tâm Pj chênh với rj không quá 0,1). Hai vị trí khả dĩ cách nhau không quá 0,1 mét được coi là một.

Nếu mọi đường tròn đều trùng nhau (kể cả khi N=1) hoặc có từ hai vị trí khả dĩ trở lên thì tín hiệu không đủ thông tin để xác định vị trí nhận. Nếu không có vị trí khả dĩ nào thì các tín hiệu mâu thuẫn. Nếu có đúng một vị trí khả dĩ thì đó là vị trí nhận.

Hình 2 của đề gốc minh hoạ ví dụ 1 (toạ độ ghi cạnh mỗi điểm): tại thời điểm t=0 ba nguồn ở A(−100,350), B(350,−100) và C(350,800). Thiết bị GPS nhận được tín hiệu mà cả ba nguồn phát tại thời điểm 1,75, khi chúng ở A′, B′, C′ (nói chung các tín hiệu có thể được phát ở những thời điểm khác nhau). Tín hiệu của ba nguồn gặp nhau tại D ở thời điểm t=2,53571, nên D là vị trí nhận. Từ D, hướng la bàn 45 độ dẫn tới điểm đích (1050,1050).

graph directed
7
1 2
3 4
5 6
2 7
4 7
6 7
name 1 A
name 2 A'
name 3 B
name 4 B'
name 5 C
name 6 C'
name 7 D
label 1 (-100, 350)
label 2 (75, 350)
label 3 (350, -100)
label 4 (350, 75)
label 5 (350, 800)
label 6 (350, 625)
label 7 (350, 350)
highlight red 7
pos 1 0 225
pos 2 88 225
pos 3 225 450
pos 4 225 363
pos 5 225 0
pos 6 225 88
pos 7 225 225

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 một số nguyên N (1≤N≤10) là số nguồn tín hiệu, tiếp theo là ba số thực t, x và y: t là thời điểm chính xác (theo giờ của thiết bị) mà mọi tín hiệu được nhận, tính bằng giây kể từ thời điểm gốc (thời điểm 0); x và y là toạ độ của điểm đích trên mặt phẳng.

Mỗi dòng trong N dòng tiếp theo chứa bốn số thực mô tả một nguồn tín hiệu. Hai số đầu là vị trí đã biết của nguồn tại thời điểm gốc. Số thứ ba là hướng di chuyển của nguồn, cho dưới dạng hướng la bàn D (0≤D<360). Số thứ tư là thời điểm được mã hoá trong tín hiệu, tức thời điểm tín hiệu được phát, tính bằng giây kể từ thời điểm gốc.

Sau bộ test cuối cùng là một dòng chứa bốn số 0.

Dữ liệu ra

Với bộ test thứ k (k=1,2,…), in một dòng bắt đầu bằng Trial k:, theo sau là:

  • H degrees, với H là hướng la bàn từ vị trí nhận tới điểm đích, làm tròn tới số nguyên gần nhất (hướng la bàn nằm trong [0,360); nếu làm tròn được 360 thì in 0);
  • Inconclusive nếu tín hiệu không đủ thông tin để xác định vị trí nhận (có nhiều hơn một vị trí phù hợp với các tín hiệu);
  • Inconsistent nếu các tín hiệu mâu thuẫn (không có vị trí nào phù hợp với các tín hiệu);
  • Arrived nếu vị trí nhận cách điểm đích không quá 0,1 mét.

Khi kết quả là Inconclusive hoặc Inconsistent thì không cần xét trường hợp Arrived.

Ràng buộc

  • 1≤N≤10; mọi số thực trong dữ liệu có giá trị tuyệt đối nhỏ hơn 10000 và có không quá 5 chữ số sau dấu thập phân; 0≤Di<360; Ti≥0.
  • Mọi bán kính ri=350(t−Ti) đều không nhỏ hơn 100.
  • Mỗi file có không quá 1000 bộ test.
  • Dữ liệu được chọn để đáp án không phụ thuộc vào sai số tính toán:
    • Hai đường tròn bất kỳ hoặc có tâm cách nhau không quá 0,01 và bán kính chênh nhau không quá 0,01; hoặc tiếp xúc với |d−(r1+r2)|≤0,01 hay |d−|r1−r2||≤0,01 và d≥1; hoặc có |d−(r1+r2)|≥1 và |d−|r1−r2||≥1, khi đó nếu cắt nhau thì góc cắt không nhỏ hơn 1 độ.
    • Mỗi điểm chung của hai đường tròn không trùng nhau cách mỗi đường tròn Cj không quá 0,01 mét hoặc ít nhất 1 mét; hai vị trí khả dĩ cách nhau không quá 0,01 mét hoặc ít nhất 1 mét.
    • Nếu chỉ xét các điểm chung của riêng một cặp đường tròn không trùng nhau (bất kỳ cặp nào) thì vẫn thu được cùng số vị trí khả dĩ và cùng vị trí nhận.
    • Khi vị trí nhận xác định duy nhất, nó cách điểm đích không quá 0,01 mét hoặc ít nhất 1 mét, và hướng la bàn sau khi làm tròn không đổi nếu vị trí nhận dịch đi không quá 0,01 mét.

Ví dụ

Input Output Giải thích
3 2.53571 1050.0 1050.0
-100.0 350.0 90.0 1.75
350.0 -100.0 0.0 1.75
350.0 800.0 180.0 1.75
2 2.0 1050.0 1050.0
-100.0 350.0 90.0 1.0
350.0 -100.0 0.0 1.0
0 0 0 0
Trial 1: 45 degrees
Trial 2: Inconclusive
Bộ test 1 ứng với hình trên: A′=(75,350), B′=(350,75), C′=(350,625), ba bán kính đều xấp xỉ 275; D=(350,350). Bộ test 2: hai đường tròn tâm (0,350) và (350,0) cùng bán kính 350 cắt nhau tại (0,0) và (350,350).
3 2.0 350.0 350.0
-100.0 350.0 90.0 1.0
350.0 -100.0 0.0 1.0
350.0 800.0 180.0 1.0
3 2.0 0.0 0.0
-100.0 350.0 90.0 1.0
350.0 -100.0 0.0 1.0
0.0 0.0 0.0 1.5
2 1.0 5.0 5.0
0.0 -50.0 0.0 0.5
-50.0 0.0 90.0 0.5
3 2.0 349.0 1000.0
-100.0 350.0 90.0 1.0
350.0 -100.0 0.0 1.0
350.0 800.0 180.0 1.0
0 0 0 0
Trial 1: Arrived
Trial 2: Inconsistent
Trial 3: Inconclusive
Trial 4: 0 degrees
Ví dụ tự thêm. Bộ test 1: đường tròn thứ ba (tâm (350,700), bán kính 350) tiếp xúc với đường tròn tâm (350,0) tại (350,350) và loại giao điểm (0,0); vị trí nhận trùng điểm đích. Bộ test 2: đường tròn tâm (0,150) bán kính 175 không đi qua (0,0) hay (350,350). Bộ test 3: hai tín hiệu cho cùng một đường tròn tâm (0,0) bán kính 175. Bộ test 4: vị trí nhận (350,350), hướng la bàn xấp xỉ 359,91 làm tròn thành 360 nên in 0.

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