Chip Routing
Time limit1sMemory limit128 MB
Assign each marked point on a square chip a direction toward a side so that drawn segments never cross or pass through other points, minimizing the total segment length.
- Level
Hard9 of 10
- Topics
- Dynamic programming, Greedy, Geometry, Sorting
- Solved
- No attempts yet
Problem
A square chip is placed on a coordinate plane. Its lower-left corner is at the origin, and its upper-right corner is at a point with integer coordinates.
Several points on the chip are marked. For each marked point, draw exactly one horizontal or vertical line segment from that point to one side of the chip. A segment must not contain any other marked point, and no two drawn segments may intersect.
Find such segments so that the sum of their lengths is as small as possible.
Input
The first line contains an integer A (2 <= A <= 30), the side length of the square chip.
The second line contains an integer N (1 <= N <= 100), the number of marked points.
Each of the next N lines contains two integers X and Y (1 <= X, Y <= A - 1), the coordinates of one marked point. No two marked points have the same pair of coordinates.
Output
If a solution exists, print the minimum possible sum of segment lengths on the first line.
Then print N lines. The i-th of these lines must contain one of GORE (up), DOLJE (down), LIJEVO (left), or DESNO (right), indicating which side the i-th input point is connected to.
If there is more than one optimal solution, print any one of them.
If no solution exists, print only -1.