Problem Description

Dongdong rides his bicycle home every day along a long and narrow tree-lined path. Because the road has been poorly maintained for many years, it has become very uneven. Although Dongdong bumps a lot each time, he still treats riding through the path as a kind of fun.

Because of the bumps, the route Dongdong takes home is a curve that goes up and down. Dongdong wants to know: how long is this curve exactly? More precisely, Dongdong wants to know the length of the path traveled by the axle (the center of the circle) of his bicycle’s front wheel from the start of the path to the end of the path.

Dongdong measured the road surface. He simplified the road into straight line segments of different lengths. These segments are connected end to end and lie in the same plane. He also built a Cartesian coordinate system in this plane and computed the coordinates of all segment endpoints.

Assume that during the ride, the front wheel always moves forward while staying in contact with the road surface.

Figure $1$ shows a simple example of a road surface, where the blue solid line is the road surface and the red dashed line is the path traveled by the wheel axle. In this example, the front wheel axle starts from point $A$, moves horizontally to point $B$, then goes around point $F$ on the ground to point $C$ (forming a circular arc), then goes downhill along a straight line to point $D$, and finally moves horizontally to point $E$. In this figure, the ground coordinates in order are: $(0,0),(2,0),(4,-1),(6,-1)$. The front wheel radius is $1.50$. The distances traveled by the front wheel axle are:

$AB=2.0000$; arc length $BC=0.6955$; $CD=1.8820$; $DE=1.6459$.

The total length is $6.2233$.

Figure $2$ shows a more complex example of a road surface. In this example, the wheel starts going uphill (at point $D$) before finishing the first downhill. Then at the peak of the slope, it needs to go around a larger circular arc from $E$ to $F$. In this figure, the front wheel radius is $1$. The length of each part is:

$AB=3.0000$; arc length $BC=0.9828$; $CD=1.1913$; $DE=2.6848$; arc length $EF=2.6224$; $FG=2.4415$; $GH=2.2792$.

The total length is $15.2021$.

Now you are given the wheel radius and the description of the road surface. Please compute the total length of the wheel axle trajectory.

Input Format

The first line contains an integer $n$ and a real number $r$, separated by a space, representing the number of coordinate points describing the road surface and the radius of the wheel.

The next $n$ lines each contain two real numbers. In the $i$-th line, the two real numbers $x_i,y_i$ represent the coordinates of the $i$-th point describing the road surface.

The road surface is defined as the polyline formed by connecting all the given road surface points in order. The given road surface always satisfies the following properties:

• The first coordinate point is always $(0,0)$.
• The $y$-coordinates of the first point and the second point are the same.
• The $y$-coordinates of the last point and the second-to-last point are the same.
• The distance between the first point and the second point is at least the wheel radius.
• The distance between the last point and the second-to-last point is at least the wheel radius.
• The $x$-coordinate of each subsequent point is greater than that of the previous point, i.e., for all $i$, $x_{i+1}>x_i$.

Output Format

Output a real number, rounded to two decimal places, representing the total length traveled by the wheel axle.

Your result must be exactly the same as the reference answer to get points. The testdata guarantees that the third digit after the decimal point of the exact value is not $4$ or $5$.

4 1.50
0.00 0.00
2.00 0.00
4.00 -1.00
6.00 -1.00

6.22

6 1.00
0.00 0.00
3.00 0.00
5.00 -3.00
6.00 2.00
7.00 -1.00
10.00 -1.00

15.20

Hint

For $20\%$ of the testdata, $n=4$.

For $40\%$ of the testdata, $n \le 10$.

For $100\%$ of the testdata, $4 \le n \le 100$, $0.5 \le r \le 20.0$, $x_i \le 2000.0$, $-2000.0 \le y_i \le 2000.0$.

Time limit: 1 second, 64 MB. Lanqiao Cup 2013, the 4th National Finals.

Translated by ChatGPT 5