2072. Atlas of Khorezmstan
The country of Khorezmstan is preparing to publish its first comprehensive atlas. It has many maps of different regions, compiled by expedition members. The maps overlap, and often the same territory is shown on more than one map. The publishers faced a problem: all these maps had to be placed in the atlas so that no area was shown twice. That is, if two maps partially depicted the same territory, they should be combined and their contents displayed on one page. In order to save paper, the publishers decided that there should be no overlapping maps on the atlas page.
Your task — create an algorithm that will help determine the minimum number of "atlas pages" needed to accommodate all available maps, taking into account their overlaps and the coordinates of the areas depicted on each page. It is also necessary to indicate the sources - footnotes to the original maps - on each atlas page. In this case, a rectangular area of arbitrary size can be located on an atlas page, which may contain "unknown" territories, the main thing is that all intersecting maps are on the same page.
Each map is a rectangle with sides parallel to the coordinate axes. For simplicity, we will neglect the curvature of the earth and assume that our fragments are already formatted into rectangles with acceptable distortions.
Input
The number of cards is given in the first line,n(1≤n≤1000).
The next n lines are given by the diagonals of the rectangles,x1,y1,x2,y2(1≤x1,y1,x2,y2≤105),x1<x2,y1<y2,x1≠x2 andy1≠y2.
Output
In the first line, output the minimum number of atlas pages.
In the following lines, output:
- In the first line, the coordinates of the atlas page diagonals.
- In the second line, the numbers of maps from the original array that ended up on this page.
The order of the "pages" in the answer does not matter, the editors will place them in the right order after you. Also, the order of the source map indexes for each page does not matter, the editors will place the links to the sources in the order they need themselves.
If there are several solutions, output the solution with the minimum total area of the atlas pages
Sample input 1
3 4 4 8 8 6 6 10 10 4 12 8 16
Sample output 1
2 4 4 10 10 1 2 4 12 8 16 3
Login to be able to submit.