Author: | I. Tufanov | Time limit: | 3 sec | |
Input file: | input.txt | Memory limit: | 256 Mb | |
Output file: | output.txt |
Multi-vehicle cooperation is a hot topic in contemporary underwater robotics. Often a group of vehicles can finish the mission faster than just one. But you have to implement sophisticated control techniques to benefit from the cooperation.
Consider vehicles and tasks they should accomplish. Each task should be accomplished by exactly one vehicle. Each task is a track that a vehicle should follow. The task number is defined by two edge points and , and length ().
Vehicle is allowed to follow a track in any direction — either from to or from to . In both cases the length of the path will be .
A plan is a sequence of tasks for each vehicle in order of execution. Every task in the plan is followed either in direct order ( to ) or in reverse order (from to ). Each task should appear exactly once in the whole plan.
The -th vehicle has a starting point . Vehicle executes its tasks according to its part of a plan. When a vehicle accomplishes one task, it goes to the start point of the next one, moving along the straight line. When all tasks assigned to a vehicle are done, it stops. Vehicle path length is a total path traveled by the vehicle during the plan execution. Plan length is a maximal vehicle path length of all vehicles in the plan.
Your program must, given vehicles and tasks, find a plan of minimal length.
Assume that vehicles operate on a plane (plane of constant depth) and that the vehicle size may be ignored.
Each point in the input file is described with two integers — its and coordinates.
On the first line of input file there are integers . Following lines describe starting points .
Next lines describe tasks, each task descriptions consisting of points , and path length .
Output file must describe a plan of minimal length. If there several such plans, output any of them.
Plan description consists of blocks, each describes a sequence of tasks for one vehicle. block starts with non-negative integer , followed by pairs . Here denotes a number of -th task for -th vehicle, it is an integer in range . The is either or : stands for passing from to , stands for passing from to .
; ;
All coordinates are integers in range .
No. | Input file (input.txt ) |
Output file (output.txt ) |
---|---|---|
1 |
|
|