|
|
Từ tập các bài có trên SPOJ (diva)
2970. Computer lab
Mã bài: WIFI
|
Phòng máy
Cuộc thi ACM sắp tới tại thành phố Hồ Chí Minh sẽ có N ðội thi. Ban tổ chức bố trí N máy thi cho các ðội, ðội i ngồi tại vị trí xi yi. Ðể các ðội có thể truy cập hệ thống nộp bài dễ dàng, ban tổ chức bố trí M access point. Ban tổ chức muốn tổ chức phòng máy sao cho:
- Mỗi máy tính ðược kết nối với ðúng 1 access point.
- Số lượng máy kết nối với các access point chênh lệch không quá 1.
- Tổng ðộ "chập chờn" của mạng là nhỏ nhất. Ðộ chập chờn của một máy ðược tính bằng bình phương khoảng cách giữa máy ðó với access point mà máy ðó kết nối tới.
Dữ liệu
- Dòng thứ nhất ghi 2 số M và N.
- M dòng tiếp theo, mỗi dòng ghi 2 số là tọa ðộ của các access point.
- N dòng tiếp theo, mỗi dòng ghi 2 số là tọa ðộ của các máy tính.
Kết quả
- Dòng thứ nhất ghi ra tổng ðộ chập chờn của mạng nhỏ nhất có thể.
- Dòng thứ 2 ghi N số. Số thứ i là số hiệu của access point mà máy thứ i kết nối tới.
Ví dụ
Dữ liệu
2 3
0 0
2 1
1 0
1 1
1 2
Kết quả
4
1 2 2
Hình vẽ dưới ðây mô tả test ví dụ trên. Các máy tính là các hình vuông màu ðen, các access point là các hình vuông màu trắng.
Giới hạn
1 ≤ N ≤ 200, 1 ≤ M ≤ 50. Các tọa ðộ là nguyên và trị tuyệt ðối không quá 1000.
| Được gửi lên bởi: | VOJ Team |
| Ngày: | 2008-09-05 |
| Thời gian chạy: | 0.5s
|
| Giới hạn mã nguồn: | 50000B |
| Ngôn ngữ cho phép: | Tất cả ngoại trừ: AWK C++ 4.3.2 CLOJ ERL F# GO JS PERL 6 PYTH 3.1.2 SCALA SED TCL |
| Nguồn bài: | VNOI Marathon '08 - Round 12/DivA
Problem Setter: Lê Ðôn Khuê |
|
|
|
|
