Description

On a plane, there is a square and a circle. Given the coordinates of two opposite vertices of the square, and the center coordinates and radius of the circle, find the area common to the square and the circle.

Input Format

The first two lines contain the coordinates of two opposite vertices of the square $(x_1,y_1)$ and $(x_2,y_2)$. The third line contains the circle center coordinates $(x_3,y_3)$ and the radius $r$, all of which are real numbers.

Output Format

Output the common area of the two shapes, to two digits after the decimal point.

0 5.0
10.00 -5
3.0 1 4.00

46.64

Hint

Constraints

For $100\%$ of the testdata, $-1200.00 \le x_i,y_i \le 1200.00$, $0 < r \le 200.00$.

Scoring

The score for this problem follows the original BOI settings, with a full score of $30$.

Notes

This problem comes from Day 1:A SQUARE AND A CIRCLE of the Baltic Olympiad in Informatics 1996.
Translated and organized by @求学的企鹅.

Translated by ChatGPT 5