This page is still under construction.

Parts of this page are still being built. What you see may change.

Abstract Art

Time limit2sMemory limit512 MB

Summary
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:

  1. the total amount of paint used
  2. 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 nn (1≤n≤1001 \le n \le 100), the number of polygons to be painted. Each of the next nn lines describes one painted polygon. A line starts with an integer mm (3≤m≤203 \le m \le 20), the number of sides of the polygon, followed by mm pairs of integers xx yy (0≤x,y≤10000 \le x, y \le 1000) 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 258.5258.5 is written as 258.500000.

Examples3

  1. Example 1

    Input
    3
    8 7 10 7 17 10 20 17 20 20 17 20 10 17 7 10 7
    4 0 0 0 8 8 8 8 0
    4 3 3 3 13 13 13 13 3
    
    Expected output
    315.000000 258.500000
    
  2. Example 2

    Input
    1
    3 0 0 1000 0 0 1000
    
    Expected output
    500000.000000 500000.000000
    
  3. Example 3

    Input
    2
    8 0 0 30 0 30 10 10 10 10 20 30 20 30 30 0 30
    4 20 5 40 5 40 25 20 25
    
    Expected output
    1100.000000 1000.000000