trang chủ / đề bài / icpc26_mb_k

Ă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 n 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ứ i nằm ở tọa độ (xi,yi) và có mức độ quan trọng truyền tin (trọng số) là wi.

Để kết nối tất cả các trạm, bạn được phép xây dựng và đặt m ă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 độ (X1,Y1),(X2,Y2),…,(Xm,Ym), 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:

Cost=∑i=1nwimin1≤j≤m(xi−Xj)2+(yi−Yj)2

Hãy xác định tọa độ của m ă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 n và m (1≤m≤n≤2000): số trạm đo xa và số ăng-ten chuyển tiếp cần đặt.
  • Mỗi dòng trong n dòng tiếp theo gồm ba số thực xi, yi và wi (|xi|,|yi|≤105; 1≤wi≤109): hoành độ, tung độ và trọng số của trạm đo xa thứ i.

Dữ liệu ra

In ra m dòng. Dòng thứ j gồm hai số thực Xj và Yj: tọa độ của ăng-ten thứ j. Mọi tọa độ phải có giá trị tuyệt đối không vượt quá 106.

Cách chấm: gọi A là tổng chi phí của cách bố trí bạn in ra, B 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 A≤B, hoặc nếu chênh lệch tương đối giữa A và B không vượt quá 10−2, tức là:

|A−B|max(1,B)≤10−2

Ràng buộc

  • 1≤m≤n≤2000.
  • |xi|,|yi|≤105; 1≤wi≤109.
  • Tọa độ in ra: |Xj|,|Yj|≤106.

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à 2+2=22. 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í 1+1=2. Ăng-ten thứ hai đặt ngay tại trạm nặng (10,2), trạm (10,0) chịu chi phí 1·2=2. Tổng chi phí là 4.
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 4; ă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ỉ 6,9282.

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