Problem hidden
This problem was hidden by Editorial Board member probably because it has incorrect language version or invalid test data, or description of the problem is not clear.

WIFI - Computer lab

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.


Added by:VOJ Team
Date:2008-09-05
Time limit:0.100s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 SCM qobi VB.NET
Resource:VNOI Marathon '08 - Round 12/DivA
Problem Setter: Lê Đôn Khuê

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.