Contaminated Ecosystem Area

Aqueous Contaminate Management monitors the pollution discharged into water bodies. The pollution source is located at the origin \((0,0)\) on the shoreline (the \(x\)-axis), and its spread is modeled by a semicircle (i.e. the set \(\{(x,y): y\ge0, x^2+y^2\le R^2\}\)). The ecosystem of concern is given by a polygon. Your task is to compute the area of the ecosystem that is contaminated by finding the area of the intersection between the ecosystem polygon and the semicircular pollution region.

Input/Output Details:

The input consists of an integer \(n\) (the number of vertices of the polygon) followed by \(n\) lines each containing two real numbers representing the coordinates of the polygon vertices in order, and finally a real number \(R\) (the radius of the semicircular pollution spread). The output is a real number representing the contaminated area. Answers within an absolute or relative error of \(10^{-6}\) are accepted.

The following figure illustrates the scenario:

Figure J.1: The shoreline is on the \(x\)-axis, the pollution source is at \((0,0)\), the semicircular arc represents the polluted water, and the dark blue region indicates the intersection with the ecosystem (polygon).

inputFormat

The first line contains an integer \(n\) (\(n \ge 3\)), the number of vertices of the ecosystem polygon. The next \(n\) lines each contain two real numbers \(x\) and \(y\) representing the coordinates of a vertex (in order). The last line contains a real number \(R\) representing the radius of the pollution semicircle. Note that the pollution region is defined as \(\{(x,y): y\ge 0, x^2+y^2\le R^2\}\).

outputFormat

Output a single real number – the area of the contaminated part of the ecosystem (i.e. the area of intersection between the ecosystem polygon and the pollution semicircular region). The answer is accepted if it has an absolute or relative error of at most \(10^{-6}\).

sample

4
-1 1
1 1
1 3
-1 3
5

4.000000