Painting polygon outlines
Time limit1sMemory limit512 MB
For each polygon side, split it at intersections with later polygons, then sum over the pieces where the depth t counts how many later polygons contain the piece.
- Level
Hard8 of 10
- Topics
- Geometry, Implementation, Brute force
- Solved
- No attempts yet
Problem
Adrian paints convex polygons on the coordinate plane with watercolors. He has no time to fill their interiors, but he still wants the drawing order to show, so the shade of each point on a polygon boundary depends on how many polygons cover that point. Say Adrian draws the polygons in this order. He paints a segment of polygon with shade if that segment, except possibly its endpoints, lies inside exactly of the later polygons .
Painting a segment with shade costs units of black paint per unit of length. Compute the total amount of paint Adrian needs in order to draw all the polygons.
Input
The first line contains the number of polygons (). Then blocks follow, and the -th block describes polygon . The first line of a block contains the number of vertices (). Each of the next lines contains two integers and (), the coordinates of one vertex. The vertices are given counterclockwise, every polygon is convex, and no two consecutive sides are parallel.
Two different polygons never touch at a vertex or along a side. More precisely, if and are sides of different polygons and , then and either have no common point at all, or they meet in exactly one point that lies in the interior of and in the interior of .
Output
Print the total amount of paint on one line, rounded to exactly six digits after the decimal point.
Notes
The picture for the first example.

The picture for the second example.
