WIFI - Phòng máy
Giới hạn- Thời gian: 0.1s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
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í x i y i . Để 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.
- Người up: voj
- Nguồn bài: VNOI Marathon '08 - Round 12/DivAProblem Setter: Lê Ðôn Khuê