Problem F
Square Pie
You are working on an OCR (Optical Character Recognition) application to convert scanned images into text format. In addition to just being able to parse text, you plan to have your software recognize graphs and transcribe them in a meaningful way. Having already handled histograms, bar graphs, scatter plots and regular pie charts, you have now worked your way to square pie charts.
A square pie chart consists of a rectangle subdivided into regions by horizontal or vertical lines. Just like a regular pie chart, the different regions represents how large fractions of something (e.g., baked desserts) are taken up by various subcategories (e.g., pies, cookies, etc). See the figure below for an example.
The module you are working on will be given a set of horizontal and vertical line segments forming a square pie chart, and should compute the sizes of the different regions of the chart.
The set of line segments is guaranteed to have been constructed as described above. In other words, four of them form a rectangle constituting the boundary of the square pie chart, and then each remaining line segment divides one rectangle into two smaller ones. Note that this means that the line segments do not intersect, except that the endpoints of each line segment touches some other line segment. However, the order of the line segments in the input is completely arbitrary and you can not assume that they are given in the order they were drawn.
Input
The first line of input consists of a single integer
Warning
This problem has somewhat large amounts of input and output. We recommend you to make sure that your input and output are properly buffered in order to make the most of the few seconds of execution time that we give you.
Output
If there are
Sample Input 1 | Sample Output 1 |
---|---|
4 2 2 6 2 6 2 6 6 6 6 2 6 2 6 2 2 |
1 |
Sample Input 2 | Sample Output 2 |
---|---|
8 6 2 0 2 0 0 6 0 0 2 0 0 2 2 2 1 3 1 3 0 0 1 6 1 6 0 6 2 2 1 2 0 |
0.333333333333 0.2500 0.1666666667 0.16666666667 0.0833333333 |