Sail Shreds - 7
Time limit2sMemory limit512 MB
Place N triangles on an X by Y rectangle without rotating them so they tile it with no overlaps, then print the new position of vertex A for each triangle.
- Level
Hard8 of 10
- Topics
- Geometry, Greedy, Implementation
- Solved
- No attempts yet
Problem
During a two-day storm, a group of sailors was shipwrecked on a desert island in the Mediterranean Sea. Their radio is broken, so they cannot call for help. Their only chance of survival is to escape on a raft, and the raft needs a sail. They recovered the main sail from the wreck, but it is torn into several shreds. They must sew the shreds together to rebuild the original sail.
Each shred is a triangle. Stripes on the sail make the correct orientation of each triangle easy to identify. The shreds must keep their orientation, because a sail sewn with a wrong orientation resists wind less and might tear again. The sailors spent several hours searching for the original arrangement without success, so they asked for a program that finds one.
Each triangle is given by the plane coordinates of its three vertices. The original sail is a rectangle with width X and height Y. Move the shreds without rotating them so that the sail is rebuilt and:
- the whole rectangle is covered,
- no two triangles intersect, meaning no point lies in the interiors of two different triangles,
- no part of any triangle lies outside the rectangle.
You may assume that a solution exists for every input. In particular, the sum of the areas of the shreds equals the area of the sail. Several shreds may have the same shape.
Input
The first line contains three integers N, X, and Y separated by single spaces. X is the width and Y is the height of the sail, with 1 ≤ X, Y ≤ 1 000 000. N is the number of shreds, with 2 ≤ N ≤ 1 000.
The next N lines describe the shreds. Line i+1 contains six integers A_i,x, A_i,y, B_i,x, B_i,y, C_i,x, and C_i,y, which are the coordinates of the vertices A_i, B_i, and C_i of the i-th triangle. All coordinates satisfy 0 ≤ value ≤ 1 000 000.
The position of a triangle in the input does not matter. For example, replacing the third line with 6 6 14 5 16 6 gives the same set of shreds.
Output
Print exactly N lines. The i-th line contains two integers separated by a single space: the coordinates A_i,x and A_i,y of the point A_i after the i-th shred is moved into place. The lower left corner of the sail is (0, 0) and the upper right corner is (X, Y).