VM 08 Bài 27 - Phòng máy kỳ diệu

View as PDF

Submit solution

Points: 1.25 (partial)
Time limit: 0.25s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
VNOI Marathon '08 - Round 12/DivAProblem Setter: Lê Ðôn Khuê
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

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.

Input

  • 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.

Output

  • 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.

Giới hạn

  • ~1 \leq N \leq 200;\text{ } 1 \leq M \leq 50~.
  • Các tọa độ là nguyên và trị tuyệt đối không quá ~1000~.

Sample Input

2 3
0 0
2 1
1 0
1 1
1 2

Sample Output

4
1 2 2

Note

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.

image


Comments

Please read the guidelines before commenting.


There are no comments at the moment.