← All solutions

Shortest judge solution: 1913 bytes. Shortest team solution (during contest): 1755 bytes.

Recall that one possible way of computing the areas of a closed polygon p₁ , . . . , p_n = p₁ is to sum up the signed areas of the triangles (0, 0), p_i , p_i+1 for every line segment p_i , p_i+1 . Understanding this, one can of compute the area of pollution by simply taking all those n triangles, intersecting them with the semicircle, and again summing up their areas.

In other words, we just need to figure out how to compute the (signed) area of a triangle (0, 0), p_i , p_i+1 , intersected with a circle, with center at the origin. To do this, we find the intersections between the line segment ( p_i , p_i+1 ) with the circle, and then do a little case analysis: the intersection of the triangle with the circle consists of some smaller triangles and some circle sectors (or possibly just the original triangle or one big circle sectors). My solution uses a case analysis based on whether there are 0, 1, or 2 intersection points with the semicircle – drawing some pictures make it pretty clear what is going on.