Intersection Area of a Square and a Circle

Given a square on a plane specified by two opposite vertices and a circle defined by its center and radius, compute the area of the intersection between the square and the circle.

The square is assumed to be axis-aligned. Let the square have vertices at \( (\min(x_1,x_2),\min(y_1,y_2)) \), \( (\min(x_1,x_2),\max(y_1,y_2)) \), \( (\max(x_1,x_2),\max(y_1,y_2)) \) and \( (\max(x_1,x_2),\min(y_1,y_2)) \). The circle is given by \( (x-c_x)^2+(y-c_y)^2=r^2 \).

Your task is to determine the common area (i.e. the intersection area) of these two figures. The answer is accepted if its absolute or relative error does not exceed \(10^{-6}\).

inputFormat

The input consists of a single line containing 7 space-separated numbers: \(x_1\), \(y_1\), \(x_2\), \(y_2\), \(c_x\), \(c_y\), and \(r\). Here, \((x_1,y_1)\) and \((x_2,y_2)\) are two opposite vertices of the square, while \((c_x,c_y)\) and \(r\) denote the center and radius of the circle respectively.

outputFormat

Output a single number representing the area of intersection between the square and the circle. The answer is accepted if it is within an absolute or relative error of \(10^{-6}\).

sample

0 0 2 2 1 1 0.5

0.7853981634