St. Nicholas Day on December 6th has passed, so now Santa is also helping out in the Christmas workshop during the final sprint before Christmas. He is supposed to load the sleigh with presents. In the old days, this was no problem. Everything fit easily into the sleigh. Today, you have to stack cleverly so that even the 55-inch TV fits into the sleigh. Again and again, Santa notices that the packages don't fit in terms of width and height. "This must be solvable today with the cloud and smartphones!" grumbles Santa. And so he commissions the IT department to program an app.
Hugo and Lydia then researched collision detection. But they haven't quite understood it yet. Maybe you can help them with the task.
The input consists of rectangles in AABB (Axis-Aligned Bounding Box) form. The first rectangle gets ID 0. Then it increments.
A rectangle is defined with left right bottom top, where left, right, bottom, top are each floating-point numbers (Double) separated by a space.
First, an integer specifies the number of test cases (n).
Then the rectangles follow, starting with ID 0.
Line feed is \n.
The rectangles should be output in the defined order (from ID 0... n-1).
The output should have the form ID with [ (ID, )* ], where the IDs of the rectangles that collide with the current rectangle should also be sorted.
No comma is inserted after the last element.
3 1 2 1 2 1.5 2.5 1.5 2.5 2.25 3.25 2.25 3.25
0 with [1] 1 with [0, 2] 2 with [1]
Please log in to submit a question...
Please log in to submit a solution...