Problem Background

SHOI2012D1T2

Problem Description

A credit card is a rectangle with rounded corners, where each corner is a quarter-circle that is tangent to the two adjacent 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 may not be a polygon because it might include several arcs.

Input Format

The first line of input contains a positive integer n, representing the number of credit cards. The second line contains three real numbers a, b, and r, which respectively denote the vertical and horizontal lengths of the credit card before rounding, and the radius of the quarter-circle.

Following that, n lines each contain three real numbers x, y, and θ, representing the horizontal and vertical coordinates of the center of a credit card (the intersection of the diagonals), and the angle in radians by which the card is rotated counterclockwise around its center.

Output Format

The output consists of a single line with a real number, representing the perimeter of the convex hull, rounded to two decimal places.

Sample Input and Output

Sample Input #1

2
6.0 2.0 0.0
0.0 0.0 0.0
2.0 -2.0 1.5707963268

Sample Output #1

21.66

Sample 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

Sample Output #2

41.60

Sample 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

Sample Output #3

41.63

Notes

For Sample 1: The outlines of the two credit cards are marked with solid lines in the figure. If 1.5707963268 is considered as π/2, the perimeter of the convex hull is 16 + 4√2.

For Sample 2: See the figure for the configuration.

For Sample 3: See the figure for the configuration. The perimeter of the convex hull is approximately 41.628267652.

This problem may require the use of trigonometric functions from a math library. For those unfamiliar with their usage, refer to the following code and its output:

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.

#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;
}

Output:

0.5000000000
0.5000000000
1.0000000000
1.5707963268
1.5707963268
0.7853981634

Data Range:

见题面 Input 部分

见题面 Output 部分