A credit card is a rectangle with its four corners rounded such that each corner is a quarter-circle tangent to the two sides of the rectangle, as shown in the figure below. Given several credit cards of the same specifications on a plane, calculate the perimeter of their convex hull. Note that the convex hull is not necessarily a polygon, as it may contain several circular arcs.
Input
The first line contains a positive integer $n$, representing the number of credit cards.
The second line contains three real numbers $a, b, r$, representing the vertical length, horizontal length, and the radius of the $1/4$ circle of the credit card (before rounding), respectively.
The following $n$ lines each contain three real numbers $x, y, \theta$, representing the horizontal coordinate, vertical coordinate of the center of a credit card (the intersection of its diagonals), and the angle in radians by which it is rotated counter-clockwise around its center.
Output
Output a single line containing a real number, representing the perimeter of the convex hull, rounded to 2 decimal places.
Examples
Input 1
2 6.0 2.0 0.0 0.0 0.0 0.0 2.0 -2.0 1.5707963268
Output 1
21.66
Note 1
The outlines of the 2 credit cards in this example are marked with solid lines in the figure above.
Input 2
3 6.0 6.0 1.0 4.0 4.0 0.0 0.0 8.0 0.0 0.0 0.0 0.0
Output 2
41.60
Note 2
The outlines of the 3 credit cards in this example are marked with solid lines in the figure below.
Input 3
3 6.0 6.0 1.0 4.0 4.0 0.1745329252 0.0 8.0 0.3490658504 0.0 0.0 0.5235987756
Output 3
41.63
Note 3
The outlines of the 3 credit cards in this example are marked with solid lines in the figure below, and the perimeter of their convex hull is approximately $41.628267652$.
Constraints
| Test Case ID | $n$ | $r$ | $\theta$ |
|---|---|---|---|
| 1 | $n = 1$ | / | / |
| 2 | $n = 2$ | $r = 0.0$ | All $\theta$ are $0.0$ |
| 3 | $n = 2$ | / | All $\theta$ are $0.0$ |
| 4 | $n = 2$ | $r = 0.0$ | / |
| 5 | $n = 2$ | / | / |
| 6 | $1 \le n \le 100$ | / | All $\theta$ are $0.0$ |
| 7 | $1 \le n \le 100$ | / | / |
| 8 | $1 \le n \le 10,000$ | / | All $\theta$ are $0.0$ |
| 9 | $1 \le n \le 10,000$ | $r = 0.0$ | / |
| 10 | $1 \le n \le 10,000$ | / | / |
For 100% of the data, $0.1 \le a, b \le 1000000.0$, $0.0 \le r < \min\{a/4, b/4\}$, and for all credit cards, $|x|, |y| \le 1000000.0$ and $0 \le \theta < 2\pi$.
Note
This problem may require the use of trigonometric functions from a math library. If you are unfamiliar with their usage, you may refer to the following programs and their output results:
| Pascal Program | Output Result |
|---|---|
uses math; const Pi = 3.141592653589793; begin writeln(sin(30.0 / 180.0 * Pi) : 0 : 10); writeln(cos(60.0 / 180.0 * Pi) : 0 : 10); writeln(tan(45.0 / 180.0 * Pi) : 0 : 10); writeln(arcsin(1.0) : 0 : 10); writeln(arccos(0.0) : 0 : 10); writeln(arctan(1.0) : 0 : 10); end. |
0.5000000000 0.5000000000 1.0000000000 1.5707963268 1.5707963268 0.7853981634 |
| C++ Program | Output Result |
|---|---|
#include <iostream> #include <math.h> using namespace std; const double Pi = 3.141592653589793; int main() { cout.setf(ios::fixed); cout.precision(10); cout<<sin(30.0 / 180.0 * Pi)<<endl; cout<<cos(60.0 / 180.0 * Pi)<<endl; cout<<tan(45.0 / 180.0 * Pi)<<endl; cout<<asin(1.0)<<endl; cout<<acos(0.0)<<endl; cout<<atan(1.0)<<endl; return 0; } |
0.5000000000 0.5000000000 1.0000000000 1.5707963268 1.5707963268 0.7853981634 |