Submit | All submissions | Best solutions | Back to list |
WIFI - Computer lab |
English | Vietnamese |
The are N teams participating in the next year regional ACM contest in Ho Chi Minh city. The organization board has arranged N computers for the teams. Team i will sit at coordinates xi, yi. To help the teams access the judging system easily, the organization board has also arranged M access points. They want to setup the computer lab so that:
- Each computer is connected to exactly one access point.
- The number of computers connected to the access points are different by no more than one.
- The total "flickering number" of the network is minimized. The flickering number of a computer is measured by the square distance from this computer to the access point that it is connected to.
Input
- First line: two numbers M and N.
- In the next M lines, each line contain two numbers that are coordinates of the access points.
- In the next N lines, each line contain two numbers that are coordinates of the computers.
Output
- Line 1: print the minimum total flickering number of the network.
- Line 2: print N numbers. The ith number is the index of the access point that computer i connected to.
Example
Input 2 3 0 0 2 1 1 0 1 1 1 2 Output 4 1 2 2
The following figure represents the example test case. The computer are represented by black squares and the access points are represented by white squares.
Constraints
1 ≤ N ≤ 200, 1 ≤ M ≤ 50. Coordinates are integers having absolute values no more than 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ê |