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 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 (hướng Bắc) là chiều dương của trục , hướng la bàn (hướng Đông) là chiều dương của trục ; hướng la bàn tăng theo chiều kim đồng hồ ( là hướng Nam, chiều âm của trục ; là hướng Tây, chiều âm của trục ).
Đơ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 mét mỗi giây, còn tín hiệu phát ra lan truyền với vận tốc 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 mét: nếu hai điểm tính được cách nhau không quá 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ểm tại thời điểm và di chuyển theo hướng la bàn , nên tại thời điểm phát tín hiệu nó ở điểm
Tín hiệu được nhận tại thời điểm , nên vị trí nhận cách đúng mét, tức là nằm trên đường tròn tâm bán kính .
- Hai đường tròn được coi là trùng nhau nếu hai tâm cách nhau không quá và hai bán kính chênh nhau không quá .
- Với hai đường tròn không trùng nhau, gọi là khoảng cách hai tâm. Nếu hoặc 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 không quá mét (khoảng cách từ điểm đó tới tâm chênh với không quá ). Hai vị trí khả dĩ cách nhau không quá mét được coi là một.
Nếu mọi đường tròn đều trùng nhau (kể cả khi ) 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 ba nguồn ở , và . Thiết bị GPS nhận được tín hiệu mà cả ba nguồn phát tại thời điểm , khi chúng ở , , (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 ở thời điểm , nên là vị trí nhận. Từ , hướng la bàn độ dẫn tới điểm đích .
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 () là số nguồn tín hiệu, tiếp theo là ba số thực , và : 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 ); và là toạ độ của điểm đích trên mặt phẳng.
Mỗi dòng trong 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 (). 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ố .
Dữ liệu ra
Với bộ test thứ (), in một dòng bắt đầu bằng Trial k:, theo sau là:
H degrees, với 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 ; nếu làm tròn được thì in );Inconclusivenế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);Inconsistentnế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);Arrivednếu vị trí nhận cách điểm đích không quá 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
- ; mọi số thực trong dữ liệu có giá trị tuyệt đối nhỏ hơn và có không quá chữ số sau dấu thập phân; ; .
- Mọi bán kính đều không nhỏ hơn .
- Mỗi file có không quá 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á và bán kính chênh nhau không quá ; hoặc tiếp xúc với hay và ; hoặc có và , khi đó nếu cắt nhau thì góc cắt không nhỏ hơn độ.
- Mỗi điểm chung của hai đường tròn không trùng nhau cách mỗi đường tròn không quá mét hoặc ít nhất mét; hai vị trí khả dĩ cách nhau không quá mét hoặc ít nhất 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á mét hoặc ít nhất 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á 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: , , , ba bán kính đều xấp xỉ ; . Bộ test 2: hai đường tròn tâm và cùng bán kính cắt nhau tại và . |
| 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 , bán kính ) tiếp xúc với đường tròn tâm tại và loại giao điểm ; vị trí nhận trùng điểm đích. Bộ test 2: đường tròn tâm bán kính không đi qua hay . Bộ test 3: hai tín hiệu cho cùng một đường tròn tâm bán kính . Bộ test 4: vị trí nhận , hướng la bàn xấp xỉ làm tròn thành nên in . |
https://oj.chuyentin.pro/problem/icpcwf04_g
Bình luận