Abstract Art
Time limit2sMemory limit512 MB
Given up to 100 simple polygons with 3 to 20 vertices each, compute the sum of their areas and the area of their union, each rounded to six decimals.
- Level
Hard8 of 10
- Topics
- Geometry, Implementation, Array
- Solved
- No attempts yet
Problem
Arty has been an abstract artist since childhood, and his works take many forms. His latest (and priciest) series is known inside the abstract art community as Abstract Art. Here is one of his recent works.

Figure 1. An example of Arty's art.
Abstract Art is painted as a set of polygons that may overlap. Arty always paints one polygon completely before he moves on to the next one.
The price of a piece varies with its looks, but collectors ask for two numbers about every painting:
- the total amount of paint used
- the total area of canvas covered
The first value is larger than the second whenever two or more polygons overlap. The paint used is the sum of the areas of the polygons, and the canvas covered is the area of their union. Both follow from the list of vertices of all the polygons, but Arty cannot waste his time on such plebeian pursuits. He has great art to produce. So it is left to you.
Given every polygon that Arty paints, compute the total amount of paint used and the total area of canvas covered.
Input
The first line contains a single integer (), the number of polygons to be painted. Each of the next lines describes one painted polygon. A line starts with an integer (), the number of sides of the polygon, followed by pairs of integers () giving the coordinates of the vertices in the order they appear around the polygon. All coordinates are integers. The vertices may be listed clockwise or counterclockwise. A polygon may be concave, but no polygon crosses itself. No point on the canvas is touched by more than two polygon border segments.
Output
Print the total amount of paint used and the area of canvas covered on one line, separated by a single space. Round both values to six digits after the decimal point and always print all six digits. For example, an area of is written as 258.500000.