Submit solution
Points:
1.25 (partial)
Time limit:
0.25s
Memory limit:
512M
Input:
stdin
Output:
stdout
Problem source:
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.
Comments