Autumn has arrived, and the leaves are falling from the trees onto your tiled courtyard. Although the leaves are pretty, your courtyard is prettier, and so you decide to clean the leaves away.
Your courtyard is formed from a grid of tiles, as illustrated below; these tiles can be described by (x,y) coordinates. The leaves have fallen into n piles, each on a different tile.
You have a leaf blower that allows you to move these piles around. The leaf blower can move a pile of leaves horizontally or vertically from one tile to another. If any two piles meet, they combine to form a single (larger) pile, which you can continue to blow around as before.
You wish to combine the leaves into a single pile using as few pile movements as you can. One pile movement involves blowing a pile of leaves (of any size) to an adjacent tile.
As an example, consider the figure below. The leaves begin in four piles, located in tiles (1,2), (2,4), (3,5) and (5,3), as seen in the first diagram.
By following these steps, a total of 2+3+3=8 pile movements are used, which is the smallest number possible.
You are not required to find the best possible solution. Instead you must simply use as few pile movements as you can. Your solution will be compared against other solutions, and better solutions will score more points. See the Scoring section for details.
You are given ten input files leaf.k.in (1 <= k <= 10).
The first line of each file contains the single integer n, giving the number of piles (2 <= n <= 500). Following this are n lines, each of the form x y, giving the coordinates of a single pile of leaves. All x and y coordinates are integers in the range 1 <= x,y <= 1000.
For each input file leaf.k.in, you must produce an output file leaf.k.out that contains your solution.
Each solution file should contain one line for each pile movement, given in order from the first movement to the last. Each line should be of the form x y p q, which indicates that the pile at tile (x,y) is blown to the tile (p,q). These two tiles must be either horizontally or vertically adjacent, and all tile coordinates must remain in the range 1 <= x,y,p,q <= 1000.
4 1 2 2 4 3 5 5 3
3 5 3 4 2 4 3 4 3 4 3 3 5 3 4 3 4 3 3 3 3 3 2 3 2 3 1 3 1 3 1 2
There is no "best solution" that you are required to achieve. Instead, your score for each input scenario will be determined relative to the other contestants whom you are competing against (as well as one of the judges' solutions).
For each input scenario, the contestant who finds a valid solution using the fewest pile movements will be identified. Suppose that this contestant uses p pile movements in total. Assuming your output also contains a valid solution, it will be scored as follows:
For example, consider an input scenario for which the best solution found by any contestant uses 100 pile movements. The scoring for a valid solution would be as follows:
A solution that makes an invalid movement (for instance, moving to a non-adjacent square, or moving outside the allowed coordinate range of 1..1000) will score zero. Likewise, a solution that does not combine all of the leaves into a single pile will score zero.
If a solution makes an otherwise legal movement from an empty tile (i.e., there are no leaves to blow from that tile), this irrelevant movement will be silently ignored (but will add to your total number of pile movements).
To submit your output files, you must do the following:
On Windows systems you can create a zip file by selecting File -> New -> Compressed (zipped) Folder from within Windows Explorer, and then you can copy your output files into this new zip file.
The website will look inside the zip file and ensure that the output files are named correctly, although it will not check the formatting or layout of these files.
If you resubmit a different zip file, the old zip file will be deleted. For instance, suppose you submit a zip file with solutions to the first five scenarios, and later on you find a solution to the sixth. Your new submission must contain all six output files, since when you submit your new solutions the old ones will be thrown away.
Please contact the contact organisers at firstname.lastname@example.org if you have any questions about this procedure.