Ăng-ten chuyển tiếp không gian con hành tinh
Đề bài
Mô tả
Để thiết lập một mạng liên lạc phủ kín toàn bộ Khu vực 2026, đoàn thám hiểm cần điều phối việc truyền tin giữa trạm đo xa mặt đất đặt trên bề mặt hành tinh (được mô hình hóa như một mặt phẳng tọa độ Descartes hai chiều). Trạm đo xa thứ nằm ở tọa độ và có mức độ quan trọng truyền tin (trọng số) là .
Để kết nối tất cả các trạm, bạn được phép xây dựng và đặt ăng-ten chuyển tiếp không gian con ở các vị trí tùy ý trên mặt phẳng (các ăng-ten không nhất thiết phải ở các vị trí khác nhau).
Với một cách bố trí ăng-ten có tọa độ , tổng chi phí độ trễ liên lạc của cách bố trí này được định nghĩa là tổng, trên tất cả các trạm đo xa, của khoảng cách Euclid từ trạm đến ăng-ten gần nó nhất nhân với trọng số của trạm:
Hãy xác định tọa độ của ăng-ten chuyển tiếp sao cho tổng chi phí độ trễ là nhỏ nhất.
Dữ liệu vào
- Dòng đầu tiên gồm hai số nguyên dương và (): số trạm đo xa và số ăng-ten chuyển tiếp cần đặt.
- Mỗi dòng trong dòng tiếp theo gồm ba số thực , và (; ): hoành độ, tung độ và trọng số của trạm đo xa thứ .
Dữ liệu ra
In ra dòng. Dòng thứ gồm hai số thực và : tọa độ của ăng-ten thứ . Mọi tọa độ phải có giá trị tuyệt đối không vượt quá .
Cách chấm: gọi là tổng chi phí của cách bố trí bạn in ra, là tổng chi phí của lời giải của ban giám khảo. Lời giải được chấp nhận nếu , hoặc nếu chênh lệch tương đối giữa và không vượt quá , tức là:
Ràng buộc
- .
- ; .
- Tọa độ in ra: .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 2 1 0.0 0.0 1.0 2.0 2.0 1.0 |
1.0 1.0 | Tổng chi phí là . Mọi điểm trên đoạn nối hai trạm đều cho cùng chi phí này nên cũng được chấp nhận. |
| 4 2 0.0 0.0 1.0 0.0 2.0 1.0 10.0 0.0 1.0 10.0 2.0 3.0 |
0.0 1.0 10.0 2.0 |
Ví dụ bổ sung (không có trong đề gốc). Ăng-ten thứ nhất phục vụ hai trạm bên trái với chi phí . Ăng-ten thứ hai đặt ngay tại trạm nặng , trạm chịu chi phí . Tổng chi phí là . |
| 3 1 0.0 0.0 1.0 4.0 0.0 1.0 2.0 3.4641 1.0 |
2.0 1.1547 | Ví dụ bổ sung (không có trong đề gốc). Ba trạm tạo thành (gần đúng) một tam giác đều cạnh ; ăng-ten tốt nhất đặt ở tâm tam giác, không trùng trạm nào, tổng chi phí xấp xỉ . |
Bình luận